Алгоритм Дейкстры, использующий метки

В рассматриваемой реализации данного алгоритма массив h[1..n] является массивом меток: метка h[i]=0, если построение кратчайшего пути из вершины s в вершину i не завершено, и h[i]=1 в противном случае.

Далее

Алгоритм Дейкстры, реализованный на основе d–кучи

Далее

Структура данных для представления графа

Множество OG(u)={v: (u,v)<=E} вершин графа G, являющихся концами ребер, выходящих из u называем окрестностью вершины u. Окрестность вершины i представляем списком, элементами которого являются пары вида (j, W(i, j)). Сам граф будет представлен массивом ADJ[1..n] указателей на списки, соответствующие окрестностям вершин.

Далее

Постановка задачи

Постановка задачи

Пусть G = (V, E, W) – ориентированный граф без петель со взвешенными ребрами. Полагаем множество вершин V={1, … , n}, множество ребер E <= V*V, |E| = m и весовая функция W(u,v) каждому ребру (u, v)<=E ставит в соответствие  его вес – неотрицательное число. Требуется найти кратчайшие пути от заданной вершины s<=V до всех остальных вершин.

Далее