Шаг 2. Изменение меток

Шаг 1. Присвоение вершинам начальных меток.

Алгоритм Дейкстры.

Этап 1. Нахождение длины кратчайшего пути.

Полагаем d (s)=0*, и считаем эту метку постоянной (постоянные метки помечаем сверху звездочкой). Для остальных вершин x_i Î V, x_i¹s полагаем d (x_i)=¥ и считаем эти метки временными. Пусть, – обозначение текущей вершины.

Для каждой вершины x_i с временной меткой, непосредственно следующей за вершиной , меняем ее метку в соответствии со следующим правилом:

.