Алгоритм Беллмана_Усов_вар26. Алгоритм Беллмана
![]()
|
Алгоритм Беллмана
![]() d≤2(2) = ![]() d≤2(3) = ![]() d≤2(4) = ![]() d≤2(5) = ![]() d≤2(6) = ![]() d≤2(7) = ![]() d≤2(8) = ![]() d≤2(9) = ![]() Заполним 2 строку таблицы. Уменьшились длины путей до вершин 3, 5, 6, 7, 8, 9. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин ![]() d≤3(2) = ![]() d≤3(3) = ![]() d≤3(4) = ![]() d≤3(5) = ![]() d≤3(6) = ![]() d≤3(7) = ![]() d≤3(8) = ![]() d≤3(9) = ![]() d≤3(10) = ![]() Заполняем 3 строку таблицы. Уменьшились длины путей до вершин 6, 8. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин ![]() d≤3(2) = ![]() d≤4(3) = ![]() d≤4(6) = ![]() d≤4(7) = ![]() d≤4(9) = ![]() d≤4(10) = ![]() Заполняем 4 строку таблицы. Уменьшились длины путей до вершин 6, 10. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин ![]() d≤3(2) = ![]() d≤3(3) = ![]() d≤3(4) = ![]() d≤3(6) = ![]() d≤3(7) = ![]() d≤3(9) = ![]() Заполняем 5 строку таблицы Уменьшились длины путей до вершин 3. Значит, имеет смысл искать более короткие пути до тех вершин графа, в которые входят дуги из перечисленных вершин ![]() d≤3(5) = ![]() d≤3(7) = ![]() Заполняем 6 строку таблицы
Длины 6 строки повторяют длины 5 строки. Кратчайшие пути найдены. ![]() |