..:GraphTheory:.. [ Алгоритмы. Алгоритм Форда-Беллмана ]

$Эмблема$

Теория графов. Определения. Алгоритмы. Исходники

Алгоритмы\Алгоритм Форда-Беллмана

Кратчайшие пути из одной вершины во все вершины графа. Алгоритм Форда-Беллмана

Итак, дан граф G=(V,E), каждому ребру [i,j] которого присвоен вес C[i,j] (если ребро [i,j] не существует, то C[i,j]=∞). Требуется найти кратчайшие пути от вершины v до всех вершин графа.
Обозначим через Dist^k[u] наименьшую длину пути из v в u, проходящего менее чем через k вершин, тогда

Dist⁰[u]=C[v,u]
Dist^k+1[v]=min(Dist^k[v],min(Dist^k[i]+C[i,v]) для всех i=1..n)

Distⁿ - массив искомых расстояний. Сложность этого алгоритма O(n³), но время можно сократить до O(n²), если все веса C[i,j] неотрицательны (см. алгоритм Дейкстры).

Скачать исходник (Pascal)