адаються максимум з одного ребра, потім знайти найкоротші шляхи за умови, що ці шляхи складаються максимум з двох ребер, і т.д.
Цей алгоритм також працює поетапно, формально він може бути визначений таким чином. Введемо позначення:-вершина-джерело; (i, j) - вартість лінії від вершини i до вершини j, причому w (i, j) = 0 або w (i, j) = ВҐ , якщо дві вершини не сполучені безпосередньо, і w (i, j) => 0, якщо дві вершини сполучені безпосередньо; - максимальна кількість ребер у дорозі на поточному кроці алгоритму; (n ) - мінімальна вартість шляху від вершини s до вершини п за умови, що цей шлях складається не більше ніж з h ребер.
Алгоритм складається з двох кроків. Крок 2 повторюється до тих пір, поки вартості шляхів не перестануть змінюватися. p align="justify">. Ініціалізація: (n) = ВҐ для всіх п В№ s, (s) = 0 для всіх h.
. Оновлення. Для кожного послідовного h> = 0 і для кожного п В№ s обчислити
+1 (n) - min [Lh (j) + w (j, n)].
З'єднати вершину п з попередньою вершиною j, для якої знаходиться мінімальне значення, і видалити будь-яке з'єднання вершини п з попередньою вершиною, утворене на більш ранній ітерації. Шлях від вершини s до вершини п закінчується лінією зв'язку від вершини j до вершини п.
При h = К для кожної вершини-одержувача п алгоритм порівнює потенційний шлях від вершини s до вершини п довжиною К + 1 з шляхом, існували до кінця попередньої ітерації. Якщо попередній коротший шлях володіє меншою вартістю, то він зберігається. В іншому випадку зберігається новий шлях від вершини s до вершини п довжиною К + 1. Цей шлях складається з колії довжиною К від вершини К до якоїсь вершини j і прямої ділянки від вершини j до вершини п. У цьому випадку використовуваний шлях від вершини s до вершини j являє собою шлях, що складається з К ретрансляційних ділянок, знайдений на попередній ітерації. По завершенні роботи алгоритму обчислюється сполучна дерево графа. p align="justify"> У таблиці 2 і на малюнку 4 показаний результат застосування цього алгоритму до графа, представленому на малюнку 2.1.
Таблиця 2 - Результати роботи алгоритму Беллмана-Форда для заданого графа
hТL (2) ПутьL (3) ПутьL (4) ПутьL (5) ПутьL (6) Путь11? 1-2? -? -11-511-62 1-2 1-5 1 - 6? 1-2 ? 10 2 Березень - 1-2-3 1-5-3 1-6-3 ? 2 жовтня - 1-2-4 1-5-4? 1-511-63 1-5-3 1-5-43 8 81-2 1 -5-3-2 1-5-4-221-5-321-5-4? 1-51 81-6 1-5-3-6ІТОГ31-221-5-321-5...
