Таблица смежности в алгоритме Дейкстры

346

28 января 2017, 10:17

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

Не понимаю это: 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>, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

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

Answer 1

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

vector < vector <int> > a

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

vector<int> d (n, INF)

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

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