Single-Source Shortest Path (Arbitrary Weights) หรือ Bellman-Ford Algorithm หาระยะทางต่ำสุดจาก Source Vertex ไปยังโหนดอื่นๆ รับน้ำหนักได้ทั้งบวกและลบ ต่างจาก Dijkstra ที่รับแค่บวก
Bellman-Ford หาระยะทางแบบ Bottom-up หาระยะทางที่มี 1 Edge ก่อน แล้วเพิ่มความยาว Path ทีละขั้น
Input
Cost Matrix ของกราฟ
0 6 ∞ 7 ∞ ∞ ∞ 0 5 8 -4 ∞ -2 ∞ 0 ∞ ∞ ∞ ∞ ∞ -3 0 9 2 ∞ 7 ∞ ∞ 0
Output
Source Vertex: 2
Vert: 0 1 2 3 4
Dist: -4 -2 0 3 -6
Pred: 4 2 -1 0 1
The graph has no negative edge cycle
Algorithm
bellmanFord(dist, pred, source)
Input: Distance list, Predecessor list, Source vertex
Output: True ถ้าพบ Negative Cycle
Begin
iCount := 1
maxEdge := n * (n - 1) / 2
for all vertices v do
dist[v] := ∞; pred[v] := φ
done
dist[source] := 0
eCount := number of edges
create edge list edgeList
while iCount < n do
for i := 0 to eCount do
if dist[edgeList[i].v] > dist[edgeList[i].u] + cost[u,v] then
dist[edgeList[i].v] := dist[edgeList[i].u] + cost[u,v]
pred[edgeList[i].v] := edgeList[i].u
done
done
iCount := iCount + 1
for all vertices i do
if dist[edgeList[i].v] > dist[edgeList[i].u] + cost[u,v] then
return true
done
return false
End
ตัวอย่างโค้ด (C++)
#include <iostream>
#include <iomanip>
#define V 5
#define INF 999
using namespace std;
int costMat[V][V] = {
{0, 6, INF, 7, INF},
{INF, 0, 5, 8, -4},
{INF, -2, 0, INF, INF},
{INF, INF, -3, 0, 9},
{2, INF, 7, INF, 0}
};
typedef struct { int u, v, cost; } edge;
int bellmanFord(int *dist, int *pred, int src) {
int icount = 1, ecount, max = V*(V-1)/2;
edge edgeList[max];
for(int i = 0; i < V; i++) {
dist[i] = INF; pred[i] = -1;
}
dist[src] = 0;
ecount = makeEdgeList(edgeList);
while(icount < V) {
for(int i = 0; i < ecount; i++)
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) {
dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
pred[edgeList[i].v] = edgeList[i].u;
}
icount++;
}
for(int i = 0; i < ecount; i++)
if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v])
return 1; // negative cycle
return 0; // no negative cycle
}
int main() {
int dist[V], pred[V], source = 2, report;
report = bellmanFord(dist, pred, source);
cout << "Source Vertex: " << source << endl;
display(dist, pred);
if(report) cout << "The graph has a negative edge cycle" << endl;
else cout << "The graph has no negative edge cycle" << endl;
}
Output
Source Vertex: 2 Vert: 0 1 2 3 4 Dist: -4 -2 0 3 -6 Pred: 4 2 -1 0 1 The graph has no negative edge cycle
