Практическая часть. 
Алгоритмы теории графов: алгоритм Форда–Беллмана

Поиск минимального пути

Составим таблицу.

лi (0).	лi (1).	лi (2).	лi (3).	лi (4).	лi (5).	лi (6).
i1.	;	;	;	;	;	;	;
i2.	;	;	;	;	;	;	;
i3.	;	;	;	;	;	;	;
i4.	;	;	;	;	;	;	;
i5.	;	;	;	;	;	;	;
i6.	;	;	;	;	;	;	;
i7.	;	;	;	;	;	;	;

и будем последовательно определять ее элементы, используя рекуррентное соотношение (2) и исходя из (1).

л1(0) = 0, лi (0) = ?, i = 2, …, n.

Используя (2) определим элементы лi (k), i = 2, 3, 4, 5, 6, 7; k = 1, 2, 3, 4, 5, 6. матричный граф смежность инцидентность л2(1) = min{лj (0) + cj2}, 1? j? 7.

при j = 1 л1(0) + с12 = 0 +? = ?

при j = 2 л2(0) + с22 =? +? = ?

при j = 3 л3(0) + с32 =? + 1 = ?

при j = 4 л4(0) + с42 =? + 1 = ?

при j = 5 л5(0) + с52 =? + 2 = ?

при j = 6 л6(0) + с62 =? +? = ?

при j = 7 л7(0) + с72 =? + 2 = ?

Следовательно л2(1) = ?

л3(1) = min{лj (0) + cj3}, 1? j? 7.

при j = 1 л1(0) + с13 = 0 + 9 = 9.

при j = 2 л2(0) + с23 =? +? = ?

при j = 3 л3(0) + с33 =? +? = ?

при j = 4 л4(0) + с43 =? + 1 = ?

при j = 5 л5(0) + с53 =? +? = ?

при j = 6 л6(0) + с63 =? +? = ?

при j = 7 л7(0) + с73 =? + 1 = ?

Следовательно л2(1) = 9.

л4(1) = min{лj (0) + cj4}, 1? j? 7.

при j = 1 л1(0) + с14 = 0 +? = ?

при j = 2 л2(0) + с24 =? +? = ?

при j = 3 л3(0) + с34 =? +? = ?

при j = 4 л4(0) + с44 =? +? = ?

при j = 5 л5(0) + с54 =? + 2 = ?

при j = 6 л6(0) + с64 =? +? = ?

при j = 7 л7(0) + с74 =? +? = ?

Следовательно л4(1) = ?

л5(1) = min{лj (0) + cj5}, 1? j? 7.

при j = 1 л1(0) + с15 = 0 +? = ?

при j = 2 л2(0) + с25 =? + 1 = ?

при j = 3 л3(0) + с35 =? + 1 = ?

при j = 4 л4(0) + с45 =? +? = ?

при j = 5 л5(0) + с55 =? +? = ?

при j = 6 л6(0) + с65 =? +? = ?

при j = 7 л7(0) + с75 =? + 1 = ?

Следовательно л5(1) = ?

л6(1) = min{лj (0) + cj6}, 1? j? 7.

при j = 1 л1(0) + с16 = 0 + 2 = 2.

при j = 2 л2(0) + с26 =? + 2 = ?

при j = 3 л3(0) + с36 =? +? = ?

при j = 4 л4(0) + с46 =? + 1 = ?

при j = 5 л5(0) + с56 =? +? = ?

при j = 6 л6(0) + с66 =? +? = ?

при j = 7 л7(0) + с76 =? + 2 = ?

Следовательно л6(1) = 2.

л7(1) = min{лj (0) + cj7}, 1? j? 7.

при j = 1 л1(0) + с17 = 0 + 12 = 12.

при j = 2 л2(0) + с27 =? + 4 = ?

при j = 3 л3(0) + с37 =? + 2 = ?

при j = 4 л4(0) + с47 =? +? = ?

при j = 5 л5(0) + с57 =? +? = ?

при j = 6 л6(0) + с67 =? + 8 = ?

при j = 7 л7(0) + с77 =? +? = ?

Следовательно л7(1) = 12

л2(2) = min{лj (1) + cj2}, 1? j? 7.

при j = 1 л1(1) + с12 = 0 +? = ?

при j = 2 л2(1) + с22 =? +? = ?

при j = 3 л3(1) + с32 = 9 + 1 = 10.

при j = 4 л4(1) + с42 =? + 1 = ?

при j = 5 л5(1) + с52 =? + 2 = ?

при j = 6 л6(1) + с62 = 2 +? = ?

при j = 7 л7(1) + с72 = 12 + 2 = 14.

Следовательно л2(2) = 10.

л2(2) = min{лj (1) + cj2}, 1? j? 7.

при j = 1 л1(1) + с12 = 0 +? = ?

при j = 2 л2(1) + с22 =? +? = ?

при j = 3 л3(1) + с32 = 9 + 1 = 10.

при j = 4 л4(1) + с42 =? + 1 = ?

при j = 5 л5(1) + с52 =? + 2 = ?

при j = 6 л6(1) + с62 = 2 +? = ?

при j = 7 л7(1) + с72 = 12 + 2 = 14.

Следовательно л2(2) = 10.

л3(2) = min{лj (1) + cj3}, 1? j? 7.

при j = 1 л1(1) + с13 = 0 + 9 = 9.

при j = 2 л2(1) + с23 =? +? = ?

при j = 3 л3(1) + с33 = 9 +? = ?

при j = 4 л4(1) + с43 =? + 1 = ?

при j = 5 л5(1) + с53 =? +? = ?

при j = 6 л6(1) + с63 = 2 +? = ?

при j = 7 л7(1) + с73 = 12 + 1 = 13.

Следовательно л3(2) = 9.

л4(2) = min{лj (1) + cj4}, 1? j? 7.

при j = 1 л1(1) + с14 = 0 +? = ?

при j = 2 л2(1) + с24 =? +? = ?

при j = 3 л3(1) + с34 = 9 +? = ?

при j = 4 л4(1) + с44 =? +? = ?

при j = 5 л5(1) + с54 =? + 2 = ?

при j = 6 л6(1) + с64 = 2 +? = ?

при j = 7 л7(1) + с74 = 12 +? = ?

Следовательно л4(2) = ?

л5(2) = min{лj (1) + cj5}, 1? j? 7.

при j = 1 л1(1) + с15 = 0 +? = ?

при j = 2 л2(1) + с25 =? + 1 = ?

при j = 3 л3(1) + с35 = 9 + 1 = 10.

при j = 4 л4(1) + с45 =? +? = ?

при j = 5 л5(1) + с55 =? +? = ?

при j = 6 л6(1) + с65 = 2 + 1 = 3.

при j = 7 л7(1) + с75 = 12 + 1 = 13.

Следовательно л5(2) = 3.

л6(2) = min{лj (1) + cj6}, 1? j? 7.

при j = 1 л1(1) + с16 = 0 + 2 = 2

при j = 2 л2(1) + с26 =? + 2 = ?

при j = 3 л3(1) + с36 = 9 +? = ?

при j = 4 л4(1) + с46 =? + 1 = ?

при j = 5 л5(1) + с56 =? +? = ?

при j = 6 л6(1) + с66 = 2 +? = ?

при j = 7 л7(1) + с76 = 12 + 2 = 14.

Следовательно л6(2) = 2.

л7(2) = min{лj (1) + cj7}, 1? j? 7.

при j = 1 л1(1) + с17 = 0 + 12 = 12.

при j = 2 л2(1) + с27 =? + 4 = ?

при j = 3 л3(1) + с37 = 9 + 2 = 11.

при j = 4 л4(1) + с47 =? +? = ?

при j = 5 л5(1) + с57 =? +? = ?

при j = 6 л6(1) + с67 = 2 + 8 = 10.

при j = 7 л7(1) + с77 = 12 +? = ?

Следовательно л7(2) = 10.

л2(3) = min{лj (2) + cj2}, 1? j? 7.

при j = 1 л1(2) + с12 = 0 +? = ?

при j = 2 л2(2) + с22 = 10 +? = ?

при j = 3 л3(2) + с32 = 9 + 1 = 10.

при j = 4 л4(2) + с42 =? + 1 = ?

при j = 5 л5(2) + с52 = 3 + 2 = 5.

при j = 6 л6(2) + с62 = 2 +? = ?

при j = 7 л7(2) + с72 = 10 + 2 = 12.

Следовательно л2(3) = 5

л3(3) = min{лj (2) + cj3}, 1? j? 7.

при j = 1 л1(2) + с13 = 0 + 9 = 9.

при j = 2 л2(2) + с23 = 10 +? = ?

при j = 3 л3(2) + с33 = 9 +? = ?

при j = 4 л4(2) + с43 =? + 1 = ?

при j = 5 л5(2) + с53 = 3 +? = ?

при j = 6 л6(2) + с63 = 2 +? = ?

при j = 7 л7(2) + с73 = 10 + 1 = 11.

Следовательно л3(3) = 9.

л4(3) = min{лj (2) + cj4}, 1? j? 7.

при j = 1 л1(2) + с14 = 0 +? = ?

при j = 2 л2(2) + с24 = 10 +? = ?

при j = 3 л3(2) + с34 = 9 +? = ?

при j = 4 л4(2) + с44 =? +? = ?

при j = 5 л5(2) + с54 = 3 + 2 = 5.

при j = 6 л6(2) + с64 = 2 +? = ?

при j = 7 л7(2) + с74 = 10 +? = ?

Следовательно л4(3) = 5.

л5(3) = min{лj (2) + cj5}, 1? j? 7.

при j = 1 л1(2) + с15 = 0 +? = ?

при j = 2 л2(2) + с25 = 10 + 1 = 11.

при j = 3 л3(2) + с35 = 9 + 1 = 10.

при j = 4 л4(2) + с45 =? +? = ?

при j = 5 л5(2) + с55 = 3 +? = ?

при j = 6 л6(2) + с65 = 2 + 1 = 3.

при j = 7 л7(2) + с75 = 10 + 1 = 11.

Следовательно л5(3) = 3.

л6(3) = min{лj (2) + cj6}, 1? j? 7.

при j = 1 л1(2) + с16 = 0 + 2 = 2.

при j = 2 л2(2) + с26 = 10 + 2 = 12.

при j = 3 л3(2) + с36 = 9 +? = ?

при j = 4 л4(2) + с46 =? + 1 = ?

при j = 5 л5(2) + с56 = 3 +? = ?

при j = 6 л6(2) + с66 = 2 +? = ?

при j = 7 л7(2) + с76 = 10 + 2 = 12.

Следовательно л6(3) = 2.

л7(3) = min{лj (2) + cj7}, 1? j? 7.

при j = 1 л1(2) + с17 = 0 + 12 = 12.

при j = 2 л2(2) + с27 = 10 + 4 = 14.

при j = 3 л3(2) + с37 = 9 + 2 = 11.

при j = 4 л4(2) + с47 =? +? = ?

при j = 5 л5(2) + с57 = 3 +? = ?

при j = 6 л6(2) + с67 = 2 + 8 = 10.

при j = 7 л7(2) + с77 = 10 +? = ?

Следовательно л7(3) = 10.

л2(4) = min{лj (3) + cj2}, 1? j? 7.

при j = 1 л1(3) + с12 = 0 +? = ?

при j = 2 л2(3) + с22 = 5 +? = ?

при j = 3 л3(3) + с32 = 9 + 1 = 10.

при j = 4 л4(3) + с42 = 5 + 1 = 6.

при j = 5 л5(3) + с52 = 3 + 2 = 5.

при j = 6 л6(3) + с62 = 2 +? = ?

при j = 7 л7(3) + с72 = 10 + 2 = 12.

Следовательно л2(4) = 5.

л3(4) = min{лj (3) + cj3}, 1? j? 7.

при j = 1 л1(3) + с13 = 0 + 9 = 9.

при j = 2 л2(3) + с23 = 5 +? = ?

при j = 3 л3(3) + с33 = 9 +? = ?

при j = 4 л4(3) + с43 = 5 + 1 = 6.

при j = 5 л5(3) + с53 = 3 +? = ?

при j = 6 л6(3) + с63 = 2 +? = ?

при j = 7 л7(3) + с73 = 10 + 1 = 11.

Следовательно л3(4) = 6.

л4(4) = min{лj (3) + cj4}, 1? j? 7.

при j = 1 л1(3) + с14 = 0 +? = ?

при j = 2 л2(3) + с24 = 5 +? = ?

при j = 3 л3(3) + с34 = 9 +? = ?

при j = 4 л4(3) + с44 = 5 +? = ?

при j = 5 л5(3) + с54 = 3 + 2 = 5.

при j = 6 л6(3) + с64 = 2 +? = ?

при j = 7 л7(3) + с74 = 10 +? = ?

Следовательно л4(4) = 5

л5(4) = min{лj (3) + cj5}, 1? j? 7.

при j = 1 л1(3) + с15 = 0 +? = ?

при j = 2 л2(3) + с25 = 5 + 1 = 6.

при j = 3 л3(3) + с35 = 9 + 1 = 10.

при j = 4 л4(3) + с45 = 5 +? = ?

при j = 5 л5(3) + с55 = 3 +? = ?

при j = 6 л6(3) + с65 = 2 + 1 = 3.

при j = 7 л7(3) + с75 = 10 + 1 = 11.

Следовательно л5(4) = 3.

л6(4) = min{лj (3) + cj6}, 1? j? 7.

при j = 1 л1(3) + с16 = 0 + 2 = 2.

при j = 2 л2(3) + с26 = 5 + 2 = 7.

при j = 3 л3(3) + с36 = 9 +? = ?

при j = 4 л4(3) + с46 = 5 + 1 = 6.

при j = 5 л5(3) + с56 = 3 +? = ?

при j = 6 л6(3) + с66 = 2 +? = ?

при j = 7 л7(3) + с76 = 10 + 2 = 12.

Следовательно л6(4) = 2.

л7(4) = min{лj (3) + cj7}, 1? j? 7.

при j = 1 л1(3) + с17 = 0 + 12 = 12.

при j = 2 л2(3) + с27 = 5 + 4 = 9.

при j = 3 л3(3) + с37 = 9 + 2 = 11.

при j = 4 л4(3) + с47 = 5 +? = ?

при j = 5 л5(3) + с57 = 3 +? = ?

при j = 6 л6(3) + с67 = 2 + 8 = 10.

при j = 7 л7(3) + с77 = 10 +? = ?

Следовательно л7(4) = 9.

л2(5) = min{лj (4) + cj2}, 1? j? 7.

при j = 1 л1(4) + с12 = 0 +? = ?

при j = 2 л2(4) + с22 = 5 +? = ?

при j = 3 л3(4) + с32 = 6 + 1 = 7.

при j = 4 л4(4) + с42 = 5 + 1 = 6.

при j = 5 л5(4) + с52 = 3 + 2 = 5.

при j = 6 л6(4) + с62 = 2 +? = ?

при j = 7 л7(4) + с72 = 9 + 2 = 11.

Следовательно л2(5) = 5.

л3(5) = min{лj (4) + cj3}, 1? j? 7.

при j = 1 л1(4) + с13 = 0 + 9 = 9.

при j = 2 л2(4) + с23 = 5 +? = ?

при j = 3 л3(4) + с33 = 6 +? = ?

при j = 4 л4(4) + с43 = 5 + 1 = 6.

при j = 5 л5(4) + с53 = 3 +? = ?

при j = 6 л6(4) + с63 = 2 +? = ?

при j = 7 л7(4) + с73 = 9 + 1 = 10.

Следовательно л3(5) = 6.

л4(5) = min{лj (4) + cj4}, 1? j? 7.

при j = 1 л1(4) + с14 = 0 +? = ?

при j = 2 л2(4) + с24 = 5 +? = ?

при j = 3 л3(4) + с34 = 6 +? = ?

при j = 4 л4(4) + с44 = 5 +? = ?

при j = 5 л5(4) + с54 = 3 + 2 = 5.

при j = 6 л6(4) + с64 = 2 +? = ?

при j = 7 л7(4) + с74 = 9 +? = ?

Следовательно л4(5) = 5.

л5(5) = min{лj (4) + cj5}, 1? j? 7.

при j = 1 л1(4) + с15 = 0 +? = ?

при j = 2 л2(4) + с25 = 5 + 1 = 6.

при j = 3 л3(4) + с35 = 6 + 1 = 7.

при j = 4 л4(4) + с45 = 5 +? = ?

при j = 5 л5(4) + с55 = 3 +? = ?

при j = 6 л6(4) + с65 = 2 + 1 = 3.

при j = 7 л7(4) + с75 = 9 + 1 = 10.

Следовательно л5(5) = 3.

л6(5) = min{лj (4) + cj6}, 1? j? 7.

при j = 1 л1(4) + с16 = 0 + 2 = 2.

при j = 2 л2(4) + с26 = 5 + 2 = 7.

при j = 3 л3(4) + с36 = 6 +? = ?

при j = 4 л4(4) + с46 = 5 + 1 = 6.

при j = 5 л5(4) + с56 = 3 +? = ?

при j = 6 л6(4) + с66 = 2 +? = ?

при j = 7 л7(4) + с76 = 9 + 2 = 11.

Следовательно л6(5) = 2.

л7(5) = min{лj (4) + cj7}, 1? j? 7

при j = 1 л1(4) + с17 = 0 + 12 = 12.

при j = 2 л2(4) + с27 = 5 + 4 = 9.

при j = 3 л3(4) + с37 = 6 + 2 = 8.

при j = 4 л4(4) + с47 = 5 +? = ?

при j = 5 л5(4) + с57 = 3 +? = ?

при j = 6 л6(4) + с67 = 2 + 8 = 10.

при j = 7 л7(4) + с77 = 9 +? = ?

Следовательно л7(5) = 8.

л2(6) = min{лj (5) + cj2}, 1? j? 7.

при j = 1 л1(5) + с12 = 0 +? = ?

при j = 2 л2(5) + с22 = 5 +? = ?

при j = 3 л3(5) + с32 = 6 + 1 = 7.

при j = 4 л4(5) + с42 = 5 + 1 = 6.

при j = 5 л5(5) + с52 = 3 + 2 = 5.

при j = 6 л6(5) + с62 = 2 +? = ?

при j = 7 л7(5) + с72 = 9 + 2 = 11.

Следовательно л2(6) = 5.

л3(6) = min{лj (5) + cj3}, 1? j? 7.

при j = 1 л1(5) + с13 = 0 + 9 = 9.

при j = 2 л2(5) + с23 = 5 +? = ?

при j = 3 л3(5) + с33 = 6 +? = ?

при j = 4 л4(5) + с43 = 5 + 1 = 6.

при j = 5 л5(5) + с53 = 3 +? = ?

при j = 6 л6(5) + с63 = 2 +? = ?

при j = 7 л7(5) + с73 = 9 + 1 = 10.

Следовательно л3(6) = 6.

л4(6) = min{лj (5) + cj4}, 1? j? 7.

при j = 1 л1(5) + с14 = 0 +? = ?

при j = 2 л2(5) + с24 = 5 +? = ?

при j = 3 л3(5) + с34 = 6 +? = ?

при j = 4 л4(5) + с44 = 5 +? = ?

при j = 5 л5(5) + с54 = 3 + 2 = 5.

при j = 6 л6(5) + с64 = 2 +? = ?

при j = 7 л7(5) + с74 = 9 +? = ?

Следовательно л4(6) = 5.

л5(6) = min{лj (5) + cj5}, 1? j? 7.

при j = 1 л1(5) + с15 = 0 +? = ?

при j = 2 л2(5) + с25 = 5 + 1 = 6.

при j = 3 л3(5) + с35 = 6 + 1 = 7.

при j = 4 л4(5) + с45 = 5 +? = ?

при j = 5 л5(5) + с55 = 3 +? = ?

при j = 6 л6(5) + с65 = 2 + 1 = 3.

при j = 7 л7(5) + с75 = 9 + 1 = 10.

Следовательно л2(6) = 3.

л6(6) = min{лj (5) + cj6}, 1? j? 7.

при j = 1 л1(5) + с16 = 0 + 2 = 2.

при j = 2 л2(5) + с26 = 5 + 2 = 7.

при j = 3 л3(5) + с36 = 6 +? = ?

при j = 4 л4(5) + с46 = 5 + 1 = 6.

при j = 5 л5(5) + с56 = 3 +? = ?

при j = 6 л6(5) + с66 = 2 +? = ?

при j = 7 л7(5) + с76 = 9 + 2 = 11.

Следовательно л6(6) = 2.

л7(6) = min{лj (5) + cj7}, 1? j? 7.

при j = 1 л1(5) + с17 = 0 + 12 = 12.

при j = 2 л2(5) + с27 = 5 + 4 = 9.

при j = 3 л3(5) + с37 = 6 + 2 = 8.

при j = 4 л4(5) + с47 = 5 +? = ?

при j = 5 л5(5) + с57 = 3 +? = ?

при j = 6 л6(5) + с67 = 2 + 8 = 10.

при j = 7 л7(5) + с77 = 9 +? = ?

Следовательно л7(6) = 8.

Заполним таблицу получившимися значениями.

лi (0).	лi (1).	лi (2).	лi (3).	лi (4).	лi (5).	лi (6).
i1.
i2.
i3.
i4.
i5.
i6.
i7.

Величина л7(6) = 8 выражает длину минимального пути из х1 в х7 в нагруженном орграфе D. Найдем минимальное число k? 1, при котором выполняется равенство л7(k+1) = л7(6). Получаем, что k = 5. Таким образом, минимальное число дуг в пути среди всех минимальных путей из х1 в х7 в нагруженном орграфе D равняется 5. Определим теперь последовательность номеров i1, i2, i3, i4, i5, i6, где i1 = 7, удовлетворяющих (4), для этого используем формулу (2). Из таблицы получаем, что в качестве такой последовательности гадо взять номера 7, 3, 4, 5, 6, 1, так как л3(4) +c37 = 6 + 2 = л7(5).

л4(3) +c43 = 5 + 1 = л3(4).

л5(2) +c54 = 3 + 2 = л4(3).

л6(1) +c65 = 2 + 1 = л5(2).

л1(0) +c16 = 0 + 2 = л6(1).

Тогда х1×6×5×4×3×7 — искомый минимальный путь из х1 в х7 в нагруженном орграфе D, причем он содержит минимальное число дуг среди всех возможных минимальных путей из х1 в х7.

Построение матрицы смежности

Рисунок 3

Построение матрицы инцидентности

Произвольно обозначим ребра орграфа Х1, Х2, …, Х23, как показано на рисунке 4.

Построим матрицу инцидентности для данного орграфа.