อัลกอริทึมเบลล์แมน-ฟอร์ด (Bellman-Ford Algorithm)

อัลกอริทึมเบลล์แมน-ฟอร์ด (Bellman-Ford) ใช้หาระยะทางสั้นที่สุดจากโหนดต้นทางไปยังโหนดอื่นๆ ทุกโหนด ข้อแตกต่างจาก Dijkstra คือ รองรับน้ำหนักลบ (Negative Weight) ได้

อัลกอริทึมทำงานแบบ Bottom-Up: หาระยะทางที่มีเพียง 1 เส้นเชื่อมก่อน แล้วเพิ่มจำนวนเส้นเชื่อมทีละขั้นจนครบทุกกรณี

การรับค่าและแสดงผล

Input: เมทริกซ์ต้นทุนของกราฟ
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

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

อัลกอริทึม

bellmanFord(dist, pred, source)

Begin
  iCount := 1
  maxEdge := n * (n - 1) / 2
  
  for ทุกโหนด v do
    dist[v] := INF
    pred[v] := φ
  done
  dist[source] := 0
  
  สร้าง edgeList จากกราฟ
  
  while iCount < n do
    for i := 0 ถึง 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
      end if
    done
    iCount++
  done
  
  // ตรวจสอบ negative cycle
  for ทุกโหนด i do
    if dist[edgeList[i].v] > dist[edgeList[i].u] + cost[u,v] then
      return true  // มี negative cycle
    end if
  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;
  
  // สร้าง edgeList (โค้ดย่อ)
  ecount = 0;
  for(int i = 0; i < V; i++)
    for(int j = 0; j < V; j++)
      if(costMat[i][j] != 0 && costMat[i][j] != INF) {
        edgeList[ecount].u = i;
        edgeList[ecount].v = j;
        edgeList[ecount].cost = costMat[i][j];
        ecount++;
      }
  
  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;
  
  return 0;
}

void display(int *dist, int *pred) {
  cout << "Vert: ";
  for(int i = 0; i < V; i++) cout << setw(3) << i << " ";
  cout << endl << "Dist: ";
  for(int i = 0; i < V; i++) cout << setw(3) << dist[i] << " ";
  cout << endl << "Pred: ";
  for(int i = 0; i < V; i++) cout << setw(3) << pred[i] << " ";
}

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;
}

ผลลัพธ์

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