Алгоритм

Обозначения

V — множество вершин графа
E — множество ребер графа
w[ij] — вес (длина) ребра ij
a — вершина, расстояния от которой ищутся
U — множество посещенных вершин
d[u] — по окончании работы алгоритма равно длине кратчайшего пути из a до вершины u
p[u] — по окончании работы алгоритма содержит кратчайший путь из a в u

Псевдокод

Присвоим

Для всех отличных от a

присвоим

Пока

Пусть — вершина с минимальным d[v]

Для всех таких, что

если d[u] > d[v] + w[vu] то

изменим