Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

5.4.3. А
ЛГОРИТМ 
Ф
ОРДА
-М
УРА
-Б
ЕЛЛМАНА
 
Алгоритм Дейкстры применим для матрицы смежности с неотрица-
тельными коэффициентами (A
ij
 >= 0). Если же матрица A является матрицей 
стоимостей, то некоторые дуги могут иметь отрицательные веса. В этом слу-
чае достаточно эффективно работает алгоритм Форда-Мура-Беллмана. 
Этот алгоритм ищет в бесконтурном графе кратчайшие пути от задан-
ной вершины до всех остальных путем непосредственного решения уравне-
ния Беллмана (уравнения динамического программирования). Алгоритм да-
лек от того, чтобы быть оптимальным. 
Рассмотрим пронумерованное множество из N городов, для каждой па-
ры из которых в матрице смежности A хранится целое число, представляю-
щее цену прямого билета для проезда между этими городами. Такая матрица 
в общем случае не является симметричной, то есть стоимости проезда в пря-
мом и обратном направлениях могут различаться. В качестве минимальной 
стоимости проезда из города i в город j будем рассматривать наименьшую 
сумму цен билетов для всех проездов между всеми парами городов на этом 
пути. Эта стоимость не может превосходить значения элемента A[i, j] матри-
цы смежности и может оказаться существенно меньше. Ставится задача на-
хождения такой минимальной стоимости для заданной пары городов. 
Примечание 
Маршрут длиной, большей N, очевидно, содержит цикл. Это соображение позволяет 
ограничить поиск минимума маршрутами с длинами, не превосходящими N. Число та-
ких маршрутов конечно и стоимость проезда по любому из них ограничена снизу ну-
лем. Поэтому маршрут с наименьшей стоимостью существует. 
Выберем в качестве начального город с номером 1 и найдем наимень-
шие стоимости проезда из него во все остальные города. Будем обозначать 
через MinS(1, s, к) минимальную стоимость проезда из города 1 в город s с 
менее, чем k, пересадками. Тогда выполняется такое соотношение: 
MinS(1,s,k+1)=Min(MinS(1,s,k),MinS(1,i,k) + A[i,s])
,
i = 1..n 
Это соотношение является основой для алгоритма динамического про-
граммирования, называемым алгоритмом Форда-Беллмана. Этот алгоритм 
для узла с номером from состоит из следующих шагов. 
1.
Для всех узлов, кроме from, назначаем расстояние 
Dist
 = MaxInt, а для узла from расстояние назначаем рав-
ным нулю. 
13 / 23

---

175 
2.
Для каждого узла сохраняем значение кратчайшего пути на 
предыдущем шаге. 
3.
Для всех узлов просматриваем все ребра и если найдется ребро, 
для которого выполняется условие: A + Node[NumNode]. Old-
Dist
 < Dist, где A — стоимость проезда по ребру, то заме-
няем расстояние, и при помощи признака Ok := true отме-
чаем изменение. 
4. 
Если на шаге 3 признак Ok = true, то повторяем шаг 2, ина-
че заканчиваем алгоритм. 
Реализация этого алгоритма представлена в листинге 5.34.