อัลกอริทึม Bellman-Ford เป็นอัลกอริทึมแบบ Dynamic Programming ใช้หาเส้นทางสั้นที่สุดจากจุดเริ่มต้น (source vertex) ไปยังทุกจุดในกราฟที่มีน้ำหนัก (weighted graph) โดยใช้วิธีวนซ้ำ (iterative) พยายามหาเส้นทางสั้นที่สุดอย่างต่อเนื่อง
เสนอโดย Alfonso Shimbel ปี 1955 ปรับปรุงโดย Richard Bellman และ Lester Ford ปี 1956 และ 1958 จึงได้ชื่อ Bellman-Ford Algorithm ยังมีการปรับปรุงโดย Edward F. Moore ปี 1957 เรียกอีกชื่อว่า Bellman-Ford-Moore Algorithm
ข้อดี: จัดการ edge ที่มีน้ำหนักลบได้ (แตช้ากว่า Dijkstra)
อัลกอริทึม
Input: กราฟมีน้ำหนัก และจุดเริ่มต้น
Output: ระยะทางสั้นที่สุดจากจุดเริ่มต้นไปทุกจุด
ถ้ามี negative weight cycle จะรายงานว่าไม่สามารถคำนวณได้
ขั้นตอนที่ 1: เริ่มต้น — สร้างอาร์เรย์ dist[] ขนาดเท่าจำนวนจุด เก็บระยะทางจากจุดเริ่มต้น
ขั้นตอนที่ 2: คำนวณระยะทางสั้นที่สุด — วนซ้ำ n-1 รอบ (n = จำนวนจุด)
ขั้นตอนที่ 3: สำหรับแต่ละ edge u-v
ขั้นตอนที่ 3.1: ถ้า dist[v] > dist[u] + weight[u,v] แล้ว dist[v] = dist[u] + weight[u,v]
ขั้นตอนที่ 4: ตรวจสอบ negative cycle — ถ้าขั้นตอน 3.1 ยังทำงานได้ แสดงว่ามี negative cycle
Negative Cycle — มีเส้นทางที่สั้นกว่าการเดินทางปกติ
ตัวอย่าง
กราฟตัวอย่าง (ดูภาพในเนื้อหาเดิม) หาระยะทางสั้นจาก A ไป E
A B C D E 0 ∞ ∞ ∞ ∞ 0 -2 ∞ ∞ ∞ (A-B) 0 -2 3 ∞ ∞ (A-C) 0 -2 3 3 10
ระยะทางสั้นที่สุดคือ 10 เส้นทาง A-B-E พบ negative cycle ด้วย
ตัวอย่างโค้ด
#include <bits/stdc++.h>
struct Edge { int src, dest, weight; };
struct Graph { int V, E; struct Edge* edge; };
struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V; graph->E = E;
graph->edge = new Edge[E];
return graph;
}
void BellmanFord(struct Graph* graph, int src) {
int V = graph->V, E = graph->E;
int dist[V];
for (int i = 0; i < V; i++) dist[i] = INT_MAX;
dist[src] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
for (int i = 0; i < E; i++) {
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
printf("Graph contains negative weight cycle");
return;
}
}
printf("Vertex :\t\t\t ");
for (int i = 0; i < V; ++i) printf("%d \t", i);
printf("\nDistance From Source : ");
for (int i = 0; i < V; ++i) printf("%d \t", dist[i]);
return;
}
int main() {
int V = 5, E = 8;
struct Graph* graph = createGraph(V, E);
graph->edge[0].src = 0; graph->edge[0].dest = 1; graph->edge[0].weight = -1;
graph->edge[1].src = 0; graph->edge[1].dest = 2; graph->edge[1].weight = 4;
graph->edge[2].src = 1; graph->edge[2].dest = 2; graph->edge[2].weight = 3;
graph->edge[3].src = 1; graph->edge[3].dest = 3; graph->edge[3].weight = 2;
graph->edge[4].src = 1; graph->edge[4].dest = 4; graph->edge[4].weight = 2;
graph->edge[5].src = 3; graph->edge[5].dest = 2; graph->edge[5].weight = 5;
graph->edge[6].src = 3; graph->edge[6].dest = 1; graph->edge[6].weight = 1;
graph->edge[7].src = 4; graph->edge[7].dest = 3; graph->edge[7].weight = -3;
BellmanFord(graph, 0);
return 0;
}
ผลลัพธ์
Vertex : 0 1 2 3 4 Distance From Source : 0 -1 2 -2 1
