double arrow

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

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

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

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

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

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

.


Сейчас читают про: