38. Пример нахождения кратчайшего пути при условии, что граф неориентированный№2

Для графа (рис. 1) найти кратчайший путь от вершины 1 до вершины 10, рассматривая граф как неориентированный. Матрица смежности весов графа в этом случае имеет вид:

	1	2	3	4	5	6	7	8	9	10
	1-	3	4	2	-	-	-	-	-	-
2	3	-	-	-	-	3	-	-	-	-
3	4	-	-	-	-	6	-	-	-	-
4	2	-	-	-	5	2	-	-	-	-
5	-	-	-	5	-	1	6	-	12	-
6	-	3	6	2	1	-	8	7	-	-
7	-	-	-	-	6	8	-	-	-	4
8	-	-	-	-	-	7	-	-	6	3
9	-	-	-	-	12	-	-	6	-	11
10	-	-	-	-	-	-	4	3	11	-

Записываем выражения для функции f_i

f₁ +3 f₁ + 4 f₁ + 2

f1 = 0; f2 = min; f3 = min; f4 = min f5 + 5

f₆ + 3 f₆ + 6 f₆ + 2

f₂ + 3

_f4 + 5 f₃ + 6

f₆ + 1 f₄ + 2 f₅ + 6

f₅ = min ; f₆ = min ; f₇ = min

f₉ +12 f₅ + 1 f₆ + 8

f₇ + 6 f₇ + 8

f₈ + 7

f₇ + 4

f₆ + 7 f₅ + 12

f₈ = min ; f₉ = min ; f₁₀ = min f₈ + 3 .

f₉ + 6 f₈ + 6

f₉ + 11

Указанные целевые функции , представляют собой систему линейных алгебраических уравнений (в примере имеется 10 уравнений и 10 неизвестных).

Рассмотрим один из вариантов ее решения, учитывая, что f₁ = 0 .

Тогда имеем:

2

f₂ = 3; f₃ = 4; f₄ = min f₅ + 5 = 2;

f₆ + 2

6

7 10

f₆ + 1 7 4 4

f₅ = min f₉ +12 = min ; f₆ = min f₅ +1 = min = 4

f₇ + 6 f₆ + 1 f₇ + 1 f₅ + 1

f₈ + 7

Подставив выражение для f₆ в f₅, получим

7 f₅ = min 4 + 1 = 5.

f₅ + 1 + 1

Тогда

11 17 15

f₇ = 11; f₈ = min ; f₉ = min ; f₁₀ = min f₈ + 3 .

f₉ + 6 f₈ + 6 f₉ + 11

Подставляя f₉ в f₈, получаем

11

f₈ = min 17 + 6 = 11.

f₈ + 6 + 6

Окончательно имеем: f₉ = 17; f₁₀ = 14.