2015-01-30
709
Предположим, что узел 1 является узлом-источником и требуется найти длины кратчайших путей от узла 1 до каждого другого узла сети.
Основная идея алгоритма Беллмана-Форда состоит в том, чтобы сначала найти длины кратчайших путей при условии, что пути содержат не более одной дуги, затем длины кратчайших путей при условии, что пути содержат не более двух дуг и т.д. Кратчайший путь при условии, что путь содержит не более h дуг(ветвей),будет называться кратчайшим (≤ h) путём.
Пусть 
- длина кратчайшего (≤ h) пути от узла 1 до узла i. Будем считать, что =0 для всех h, а 
∞, если отсутствует дуга (i,j).
Алгоритм Беллмана-Форда состоит в следующем.
Вначале 
∞ для всех i≠1.
При каждом последующем h≥0
для всех i≠1.
Рис. 8.5 иллюстрирует работу алгоритма
8
1
Узел- 1 2 4 2 Длины дуг указаны
источник 4
∞
Кратчайшие пути,
использующие не более одной дуги.
∞
Кратчайшие пути,
использующие не более двух дуг.
 |
Кратчайшие пути,
использующие не более трёх дуг.
|
|
|
Итоговое дерево
кратчайших путей.
 |
Рис.8.5
Число операций алгоритма в худшем случае равно N-1,каждая операция должна быть проведена для N-1 узла, а для каждого узла минимизация осуществляется самое большее по N-1 переменной. Таким образом, в худшем случае объём вычислений записывается в виде 0(
),где N – число узлов в сети.
