double arrow

Присвоение начальных значений


Шаг 1. Положить l(s) = 0 и считать эту пометку постоянной. Положить l(xi) = ¥ " xi ¹ s и считать эти пометки временными. Положить p = s.

Обновление пометок

Шаг 2. Для всех xi Î G(P), пометки которых являются временными, изменить пометки в соответствии с выражением

l(xi) = min [l(xi), l(p) + c(p, xi)] (2)

Превращение пометки в постоянную

Шаг 3. Среди всех вершин с временными пометками найти такую xi*, для которой l(xi*) = min[l(xi)]. Считать пометку вершины xi* постоянной и положить p = xi*.

Шаг 4, а (выполняется в случае, если требуется найти лишь путь от S к t). Если p = t, то l(p) является длиной кратчайшего пути. Останов. Если p ¹ t, перейти к шагу 2.

Шаг 4,б (Выполняется в случае, если требуется найти путь от S ко всем остальным вершинам). Если все вершины отмечены как постоянные, то эти отметки дают длины кратчайших путей. Останов. Если некоторые пометки являются временными, перейти к шагу 2.

Проиллюстрируем работу алгоритма на примере графа, изображенного на рис.2.38, матрица весов которого дана в табл.2.4. Здесь каждое ребро рассматривается как пара противоположно ориентированных дуг равного веса. Требуется найти все кратчайшие пути от x1 ко всем остальным вершинам. Постоянные пометки будем обозначать знаком +.

Шаг 1. l(x1) = 0+, l(xi) = ¥ " xi ¹ x1, p = x1.


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