 |
 |
 |
 |
|
 |
 |
72
если начальная и конечная вершины соединены дугой нулевой длины), то доказываемое утверждение
очевидно. Предположим,
что оно верно для всех пунктов, помеченных за первые r итераций, т. е. тех, которые достигаются
переходом по r дугам. Тогда, если конечная вершина t помечена на (r + 1)-ой итерации, то полученный
путь также будет кратчайшим, так как данная вершина помечается в результате минимально
возможного продолжения одного из путей, полученного за предыдущие r итераций и являющегося по
предположению кратчайшим.
Отметим, что описанный алгоритм пригоден для построения кратчайших путей на
неориентированных графах.
Рассмотрим изложенный метод на конкретном примере, а именно: определим кратчайший путь из
вершины 1 в вершину 6 для неориентированной сети, показанной на рис. 3.5.
На предварительном этапе вершина 1 отмечается числом m1 = 0, а модифицированные длины
совпадают с заданными длинами дуг.
Итерация 1. Так как из вершины 1 не выходят дуги нулевой длины, дальнейшая отметка вершин
невозможна. Переходим к этапу 2. Смежными с вершиной 1 являются вершины 2 и 3. Для них
определяем
? = min{
с
~
1,2
,
с
~
1,3
}=2 и вычитаем ее из
с
~
1,2
,
с
~
1,3
. После преобразования имеем
с
~
1,2
= 0,
с
~
1,3
= 1.
Итерация 2. Помечаем вершину 2 m2 = 1 (см. рис. 3.6). Дальнейшая пометка невозможна, поэтому
переходим к этапу 2. Смежными с помеченными вершинами 1 и 2 являются вершины 3,4,5. Из чего
определяем ? = min{
с
~
1,3
,
с
~
2,3
,
с
~
2,4
,
с
~
2,5
}=1 и после соответствующего преобразования имеем