Оглавление | Назад | Глоссарий понятий
Пример 2.14.2
Рассмотрим граф, изображенный на рисунке. Требуется найти все кратчайшие пути от вершины Х1 ко всем остальным вершинам. Матрица весов приведена ниже.
 |
рис. 2.31 |
Решение
 |
 |
 |
 |
 |
 |
 |
 |
Все вершины имеют пометки.
Рис. 2.32
Найдём кратчайший путь, например, (Х1,Х2).
Вершина Х2 имеет пометку 5*. Полагая в соотношении (1) Хi = Х2, получаем I(X2')+с(Х2', Х2) = I(X2) = 5.
Единственной такой вершиной является Х7. Далее применяем ещё раз соотношение (1) и получаем путь (Х1,Х7,Х2) и т. д.
Оглавление | Назад | Глоссарий понятий
