Алгоритм

Обозначения

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

Псевдокод

Присвоим

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

присвоим

Пока

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

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

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

изменим

изменим