Алгоритм

Обозначения

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

Псевдокод

Присвоим

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

присвоим

Пока

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

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

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

изменим

изменим