ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ.

 

Задача 1. Задан граф.

v 7

v 5

v 6

v 4

v 3

v 2

v 1

v 8

 

 

Найти кратчайший путь из вершины v₁ в вершину v₈.

Решение. Используя алгоритм задачи о нахождении кратчайшего пути из v₁ в v₈ в смысле наименьшего количества ребер, получим:

1. Вершине v₁ припишем индекс 0.

2. Всем вершинам, смежным с v₁ (v₂ и v₃), припишем индекс 1.

3. Всем вершинам, смежным v₂ и v₃ и не имеющим индекса (v₅,v₄,v₆,v₇), припишем индекс 2.

4. Всем вершинам, смежным с вершинами (v₄,v₅,v₆,v₇) и не имеющим индекса v₈, припишем индекс 3.

Таким образом, вершина v₈ получила индекс 3, а значит, длина кратчайшего пути из v₁ в v₈ равна 3. Построим этот путь или пути, если их несколько.

5. Среди вершин, смежных с v₈, найдем вершины с индексом 3-1=2. Таких вершин три: v₆,v₇, v₄.

6. Среди вершин, смежных с v₄,v₆,v₇, найдем вершины с индексом 1. Таких вершин две: v₂ и v₃.

7. Среди вершин, смежных с v₂ и v₃, найдем вершины с индексом 0. Такая вершина одна и это v₁.

Таким образом, было получено три кратчайших пути длины 3. Перечислим их: 1) v₁,v₂,v₆,v₈; 2) v₁,v₃,v₇,v₈; 3) v₁,v₃,v₄,v₈.

 

 

v 7 (2)

v 5 (2)

v 6 (2)

v 4 (2)

v 3 (1)

v 2 (1)

v 1 (0)

v 8 (3)

 

Задача 2. Задан орграф.

v 5

v 6

v 7

v 3

v 4

v 1

v 2

 

Найти кратчайший путь из вершины v₁ в вершину v₆ в смысле суммы весов дуг.

Решение. Используя алгоритм решения задачи о нахождении кратчайшего пути в смысле суммы весов дуг, получим:

1. Вершине v₁ присвоим индекс 0, а всем остальным +¥.

2. Переберем вершины орграфа, смежные с вершиной v₁ и имеющие дугу из v₁ в эту же вершину. Вершине v₄ присвоим индекс 0+2=2, так как 2<+¥. Вершине v₃ присвоим индекс min {0+1, 2+2}=1, так как 1<+¥. Вершине v₂ присвоим индекс min{0+1, 2+5}=2, так как 1<+¥.

3. Аналогично проведем рассуждения для вершин орграфа, смежных с вершинами v₂,v₃,v₄. Так как в вершину v₅ ведет две дуги, то присвоим ей индекс min{1+4, 2+3}=5<+¥. Вершине v₇ присвоим индекс min{2+5, 1+3}=4<+¥.

4. Вершине v₆ присвоим индекс min{5+2, 2+6, 4+1}=4+1=5. Таким образом, кратчайший путь из вершины v₁ в v₆ в смысле суммы весов дуг равен 5.

Построим этот путь.

5. Среди вершин, смежных с вершиной v₆, найдем вершину С, для которой выполняется равенство . Такой вершиной является v₇, так как или 4+1=5.

6. Среди вершин, смежных с вершиной v₇, найдем вершину Д, для которой выполняется равенство . Такой вершиной является v₃, так как или 1+3.

7. Среди вершин, смежных с вершиной v₃, найдем такую вершину Е, для которой выполняется равенство . Такая вершина одна и это v₁.

Таким образом, мы вернулись из вершины v₆ в вершину v₁.

Запишем кратчайший путь из v₁ в v₆: v₁ v₃ v₇ v₆.

v 5 (5)

v 2 (1)

v 6

v 7(4)

v 3 (1)

v 4(2)

v 1 (0)