24
Шаг 2. Для всех
v
S (т.е. для всех неокрашенных вершин)
пересчитать
d(v) по формуле:
d(v) =
min{ d(v), d(y)+L(
y,v)} . Если все
d(v)= ∞,
перейти к шагу 5 (это означает, что в графе отсутствуют пути из
v
0
в
неокрашенные вершины).
Шаг 3. Выбрать в
S вершину w,
для которой величина
d(v) минимальна, и
положить S:=S\{
w}, т.е. окрасить вершину
w. Окрасить дугу,
ведущую в
вершину
w из вершины, которая была взята в качестве
y последний раз, когда
в менялось значение
d для
вершины w . Положить
y= w. Если S не пусто,
перейти к шагу 2, иначе к шагу 4.
Шаг 4. Конец работы алгоритма.
При графической реализации алгоритма
для графа будет построено
покрывающее дерево с корнем в вершине
v
0
(если оно существует). Если
требуется определить не сам кратчайший путь, а лишь его длину, то можно
не проводить окрашивание, а только вычислять на
каждой итерации
множество S . Расчет условно оформлять в виде таблице, как показано в
следующем примере.
Решение. Для графа, изображенного на рис. 37,
найти расстояния от
вершины v
0
до остальных вершин и построить дерево кратчайших путей с
корнем в v
0
.
Рис. 37.
Работа алгоритма будет иллюстрироваться заполнением приведенной
ниже таблицы. Кроме того, для каждой строки таблицы приводится рисунок,
соответствующий графической
реализации алгоритма; на этом рисунке
окрашенные вершины изображаются черным кружком,
окрашенные ребра
выделены жирными линиями.
25
Строка с номером ноль соответствует состоянию переменных после
выполнения шага 1. Клетка
d(v
Достарыңызбен бөлісу: 
