В графе (Рис. 1) найти длину кратчайшего пути из Х4 в Х1


Решение

Составим таблицу пошагово:

	1	2	3	4	5	6	7	8
s Х1	∞	∞	∞	∞	∞	7,X2	7,X2	7,X4
X2	∞	∞	∞	6,X5	4,X3
X3	∞	3,X4	3,X4	3,X4
t X4	0,X4
X5	∞	2,X4	2,X4
X6	∞	1,X4
X7	∞	∞	∞	9,X5	9,X5	6,X2	6,X2
X8	∞	∞	4,X6	4,X6	4,X6	4,X6

На первом шаге вершине S присваиваем метку (0, S), а остальным ( ∞). Выбираем из всех меток наименьшую (y, X4) и делаем её постоянной. Из этой «постоянной» вершины пытаемся пометить достижимые из неё вершины и присваиваем метку:
метка = min(старая метка, метка постоянной вершины + длина ребра).
Метки недостижимых вершин сохраняются. У постоянных вершин метки не меняют точки. Процесс продолжаем, пока постоянной меткой не будет помечена вершина t. Метка вершины t равна длине кратчайшего пути. В нашем случае Lмм=7.
Маршрут восстанавливаем из второй части меток, которые содержат индекс вершины, из которых они помечены.
Тогда кратчайший маршрут: (Х1, Х2, Х3, Х4) или (Х4, Х3, Х2, Х1).