Đường đi ngắn nhất đơn nguồn, trọng số tùy ý (Bellman-Ford)

Thuật toán đường đi ngắn nhất đơn nguồn (trọng số dương hoặc âm) gọi là Bellman-Ford, tìm khoảng cách nhỏ nhất từ đỉnh nguồn đến các đỉnh khác. Khác với Dijkstra: Bellman-Ford xử lý được trọng số âm.

Bellman-Ford tìm khoảng cách theo cách bottom-up. Trước tìm khoảng cách chỉ có 1 cạnh trong đường đi. Sau đó tăng độ dài đường đi để tìm tất cả giải pháp.

Đầu vào − Ma trận chi phí đồ 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 â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, đỉnh nguồn.

Đầu ra − True nếu tìm thấy chu trình âm.

Begin
    iCount := 1
    maxEdge := n * (n - 1) / 2
    for all vertices v do
        dist[v] := ∞
        pred[v] := φ
    done
    dist[source] := 0
    eCount := số cạnh trong đồ thị
    tạo danh sách cạnh 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

Ví dụ (C++)

#include 
#include 
#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 isDiagraph(){ ... }
int makeEdgeList(edge *eList){ ... }
int bellmanFord(int *dist, int *pred, int src){ ... }
void display(int *dist, int *pred){ ... }
int main(){ ... }

Đầ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