Thuật toán Bellman-Ford tìm đường đi ngắn nhất

Thuật toán Bellman-Ford được dùng để tìm khoảng cách tối thiểu từ đỉnh nguồn đến bất kỳ đỉnh nào khác. Khác biệt chính so với thuật toán Dijkstra là: Dijkstra không xử lý được trọng số âm, nhưng Bellman-Ford xử lý dễ dàng.

Bellman-Ford tìm khoảng cách theo cách bottom-up (từ dưới lên). Trước tiên, nó tìm những khoảng cách chỉ có một cạnh trong đường đi. Sau đó tăng độ dài đường đi để tìm tất cả các giải pháp có thể.

Đầu vào và Đầu ra

Đầu vào: Ma trận chi phí của đồ thị:
0  6  ∞  7  ∞
∞  0  5  8 -4
∞ -2  0  ∞  ∞
∞  ∞ -3  0  9
2  ∞  7  ∞  0
Đầu ra: Đỉnh nguồn: 2
Vert:  0  1  2  3  4
Dist: -4 -2  0  3 -6
Pred:  4  2 -1  0  1
Đồ thị không có chu trình cạnh âm

Thuật toán

bellmanFord(dist, pred, source)
Đầu vào: Danh sách khoảng cách, danh sách tiền nhiệm, và đỉnh nguồn.
Đầu ra: True khi tìm thấy chu trình âm.
Bắt đầu
  iCount := 1
  maxEdge := n * (n - 1) / 2 // n là số đỉnh
  với mọi đỉnh v của đồ thị, thực hiện
    dist[v] := ∞
    pred[v] := ∅
  kết thúc
  dist[source] := 0
  eCount := số cạnh hiện có trong đồ thị
  tạo danh sách cạnh tên edgeList
  trong khi iCount < n, thực hiện
    với i := 0 đến eCount, thực hiện
      nếu dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] cho cạnh i) thì
        dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] cho cạnh i)
        pred[edgeList[i].v] := edgeList[i].u
      kết thúc
    kết thúc
    iCount := iCount + 1
  với mọi đỉnh i trong đồ thị, thực hiện
    nếu dist[edgeList[i].v] > dist[edgeList[i].u] + (cost[u,v] cho cạnh i) thì
      trả về true
    kết thúc
  trả về false
Kết thúc

Ví dụ (C++)

#include <iostream>
#include <iomanip>
#define V 5
#define INF 999
using namespace std;

// Ma trận chi phí của đồ thị (có hướng) 5 đỉnh
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 isDiagraph() {
  // kiểm tra đồ thị có phải đồ thị có hướng không
  int i, j;
  for(i = 0; i < V; i++) {
    for(j = 0; j < V; j++) {
      if(costMat[i][j] != costMat[j][i]) {
        return 1; // đồ thị có hướng
      }
    }
  }
  return 0; // đồ thị vô hướng
}

int makeEdgeList(edge *eList) {
  // tạo danh sách cạnh từ các cạnh của đồ thị
  int count = -1;
  if(isDiagraph()) {
    for(int i = 0; i < V; i++) {
      for(int j = 0; j < V; j++) {
        if(costMat[i][j] != 0 && costMat[i][j] != INF) {
          count++;
          // tìm cạnh khi đồ thị có hướng
          eList[count].u = i;
          eList[count].v = j;
          eList[count].cost = costMat[i][j];
        }
      }
    }
  } else {
    for(int i = 0; i < V; i++) {
      for(int j = 0; j < i; j++) {
        if(costMat[i][j] != INF) {
          count++;
          // tìm cạnh khi đồ thị vô hướng
          eList[count].u = i;
          eList[count].v = j;
          eList[count].cost = costMat[i][j];
        }
      }
    }
  }
  return count+1;
}

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; // khởi tạo với vô cực
    pred[i] = -1; // không tìm thấy tiền nhiệm
  }
  dist[src] = 0; // cho đỉnh bắt đầu, khoảng cách là 0
  ecount = makeEdgeList(edgeList); // tạo danh sách cạnh
  
  while(icount < V) {
    // số lần lặp là (Đỉnh - 1)
    for(int i = 0; i < ecount; i++) {
      if(dist[edgeList[i].v] > dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v]) {
        // thư giãn cạnh và đặt tiền nhiệm
        dist[edgeList[i].v] = dist[edgeList[i].u] + costMat[edgeList[i].u][edgeList[i].v];
        pred[edgeList[i].v] = edgeList[i].u;
      }
    }
    icount++;
  }
  
  // kiểm tra chu trình âm
  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; // chỉ ra đồ thị có chu trình âm
    }
  }
  return 0; // không có chu trình âm
}

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

int main() {
  int dist[V], pred[V], source, report;
  source = 2;
  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;
}

Đầu ra

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