Пример. Найти минимальный путь из x0 в x6

Найти минимальный путь из x₀ в x₆.

1 шаг. Вершине x₀ приписывается метка l₀ =0. Всем остальным x_i приписывается l_i=¥.

2 шаг. Рассматриваем вершину x₁ и дугу x₀®x₁. Вершине x₁ приписываем метку l₁¢=l₀+l(x₀,x₁) =0+4=4.

3 шаг. Рассматриваем вершину x₃ и дугу x₀®x₃. Тогда l₃¢=l₀+l(x₀,x₃) =0+2=2.

4 шаг. Рассматриваем вершину x₂ и дугу x₀®x₂. Тогда l₂¢=l₀+l(x₀,x₂) =0+5=5.

5 шаг. Рассматриваем вершину x₅ и дугу x₀®x₅. Тогда l₅¢=l₀+l(x₀,x₅) =0+4=4.

6 шаг. Рассматриваем вершину x₄ и дугу x₁®x₄. Тогда l₄¢=l₁+l(x₁,x₄) =4+2=6.

7 шаг. Рассматриваем вершину x₆ и дугу x₄®x₆. Тогда l₆¢=l₄+l(x₄,x₆) =6+1=7.

Разметка вершин показана на рисунке кружками. Выбор дуги (x_i,x_j) при разметке вершины x_j осуществляется совершенно произвольно. Единственное ограничение: метка l_i вершины x_i не должна быть равна ¥.

8 шаг. Рассматриваем вершину x₂ и стремимся уменьшить её метку. Для этого рассматриваем все дуги, ведущие в x₂: выписываем все возможные выражения для метки l₂¢: l₂¢=l₀+l(x₀,x₂) =0+5=5.

l₂¢=l₃+l(x₃,x₂) =2+1=3.

l₂¢= min = 3, поэтому заменяем метку вершины x₂ на 3.

9 шаг. Аналогично для x₄: l₄¢=l₁+l(x₁,x₄) =4+2=6.

l₄¢=l₂+l(x₂,x₄) =3+2=5.

l₄¢= min = 5, поэтому заменяем метку вершины x₄ на 5.

10 шаг. Аналогично для x₅: l₅¢=l₃+l(x₃,x₅) =2+1=3.

l₅¢=l₄+l(x₄,x₅) =5+2=7.

l₅¢= min = 3, поэтому заменяем метку вершины x₅ на 3.

11 шаг. Аналогично для x₆: l₆¢=l₄+l(x₄,x₆) =5+1=6.

l₆¢=l₂+l(x₂,x₆) =3+3=6.

l₆¢=l₅+l(x₅,x₆) =3+5=8.

l₆¢= min = 6, поэтому заменяем метку вершины x₆ на 6.

12 шаг. Для x₁ понижение невозможно.

Дальнейшее понижение меток вершин невозможно, поэтому прекращаем разметку.

13 шаг. Ищем минимальный путь из x₆ в x₀.

(x₆ , x₄, x₂, x₃, x₀) длина пути: 2+1+2+1=6

(x₆ , x₂, x₃, x₀) длина пути: 3+2+1=6

Пример для самостоятельной работы: