Алгоритм Форда-Беллмана
Существует большое количество практических задач, сводящихся к поиску кратчайших путей в сети (графе). К их числу можно отнести: поиск кратчайшего расстояния между городами; поиск пути передачи информации, обеспечивающего минимальную стоимость или минимальное время передачи, или максимальную надежность при распространении информации в разветвленной сети.
Исходными данными для поиска кратчайшего пути в сети (графе) является матрица весов дуг заданного ориентированного графа. Это означает, что каждой дуге ( u,v )IE поставлено в соответствие некоторое вещественное число А( u,v ), называемое весом данной дуги. Длину крат-чайшего пути d ( s,t ) между вершинами s и t называют расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t , то полагают d ( s,t )=?, где ?- некоторый символ.
Большинство алгоритмов поиска расстояний между двумя фиксированными вершинами s и t включают в себя следующие действия: по данной матрице весов дуг A[ u,v ] ( u,vIV ) вычисляют некоторые верхние ограничения D[ v ] на расстояние от s до всех вершин v . На каждом шаге, если D[ v ]+A[ u,v ]<D[ v ] оценку D[ v ] улучшают: D[ v ]=D[ u ]+A[ u,v ]. Процесс прекращается, когда дальнейшее улучшение ни одного из ограничений невозможно.
Алгоритм Форда-Беллмана позволяет найти расстояние от источника до всех вершин D[ v ]= d ( s,v ), vIV ориентированного графа при условии, что граф не содержит контуров отрицательной длины ( n - количе-ство вершин в графе) [Липский,1988]. Исходными данными для этого алгоритма являются матрица весов дуг A[ u,v ].
For vIV do D[v]:=A[s,v];
D[s]:=0;
For k:=1 to n-2 do
For vaV\{s} do
For uIV do D[v]:=min(D[v],D[u]+A[u,v])
На рисунке [Бурковский,Холопкина,Райхель,Кравец,1996] приведен: (а) граф; (б) соответствующая ему матрица весов дуг; (в) результаты работы алгоритма Форда-Беллмана.
Приведенный алгоритм отыскания кратчайших путей в графах с отрицательными длинами дуг, принадлежащий Форду, Муру и Беллману, может служить одним из возможных способов обнаружения контуров отрицательной длины (или циклов в неориентированном графе) [Евстигнеев,Касьянов,1992,с.47-48].
