0

Описание алгоритма

Не понимаю это: vector < vector < pair<int,int> > > g (n); Как мне считать таблицу смежности?

И не очень понимаю эти две строки:

vector<int> d (n, INF),  p (n); //INF - const int = 10000000;
vector<char> u (n);

pair<int,int>, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

Как можно обойтись без векторов, а простыми массивами?

1
  • А чем вам вектор не обычный массив? Разве что писать дольше, но зато и плюшек больше. Используйте псевдоним через using или typedef.
    – aleks.andr
    26 янв 2017 в 5:44

2 ответа 2

0

Удобнее всего заполнять соседей i-ых вершин через вектор, потому что массив может занимать больше памяти, чем вектор(массив создает лишние пустые элементы).

#include <vector>
#include <iostream>

using namespace std;

vector <vector < pair <int, int> > > v; // v[i] будет содержать всех соседей вершины i со своими ценами

int main()
{

    int n, m; // кол-во вершин у тебя в графе и кол-во дорог в графе соответсвенно
    int A, B, сost;

    cin >> n >> m;

    v.resize(n+1); // когда мы создали вектор он был пустым, после resize он стал состоять из n+1 пустых строк куда мы будем пихать наших соседей

    for(int i = 0; i < m; ++i){

          cin >> A >> B >> cost;
          v[a].push_back(make_pair(B, cost)); // помечаем что B сосед A c ценной cost
          v[b].push_back(make_pair(A, cost)); // помечаем что А сосед B с ценной cost

    }


}
0

Обычно для матрицы смежности используют

vector < vector <int> > a

И тогда скажем a[0] - вектор вершин в которые можно попасть из нулевой вершины. Но надо хранить еще вес и потому используют пару интов. Одно число - номер вершины, другое - вес ребра.

vector<int> d (n, INF)

изначально все кратчайшие пути = бесконечность(какое-то очень большое число)

p(n) это скорее всего массив предков, т.е p[i] = вершина j такая что кратчайший путь от начальной вершины до вершины i проходит через j, т.е 0 -> ... -> j -> i

1
  • 1
    А как мне считать матрицу смежности?
    – goodalien
    26 янв 2017 в 15:56

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.