Bellman-Ford và Floyd-Warshall

Bellman-Ford và Floyd-Warshall là hai thuật toán đường đi ngắn nhất chịu được cạnh trọng số âm, điều mà Dijkstra không làm được. Bellman-Ford tìm khoảng cách từ một đỉnh nguồn trong $O(VE)$ và phát hiện được chu trình âm; Floyd-Warshall tìm khoảng cách giữa mọi cặp đỉnh trong $O(V^3)$ chỉ với ba vòng for lồng nhau. Cả hai chậm hơn Dijkstra, nhưng là lựa chọn đúng khi đồ thị có cạnh âm, khi cần kiểm tra chu trình âm, hoặc khi $V$ nhỏ (cỡ $V\le 500$) và phải trả lời rất nhiều truy vấn khoảng cách giữa hai đỉnh bất kỳ.

Ý tưởng / Trực giác

Phép nới lỏng (relaxation)

Cả hai thuật toán (và cả Dijkstra) đều xoay quanh một thao tác duy nhất: nới lỏng cạnh $u\to v$ trọng số $w$:

$$dist[v]\leftarrow min(dist[v],dist[u]+w)$$

Nghĩa là: "nếu đi tới $u$ rồi đi tiếp cạnh $u\to v$ rẻ hơn cách tốt nhất đã biết để tới $v$, thì cập nhật". Các thuật toán chỉ khác nhau ở thứ tự nới lỏng. Dijkstra nới lỏng theo thứ tự khoảng cách tăng dần, nên mỗi đỉnh chỉ cần xử lý một lần; nhưng thứ tự đó chỉ đúng khi mọi cạnh không âm. Bellman-Ford từ bỏ việc chọn thứ tự thông minh: nó nới lỏng tất cả các cạnh, lặp lại nhiều vòng, nên đúng với mọi trọng số.

Bellman-Ford: vì sao $N-1$ vòng là đủ

Nhận xét then chốt: nếu đồ thị không có chu trình âm, luôn có một đường đi ngắn nhất là đường đi đơn (không lặp đỉnh), vì cắt bỏ một chu trình có tổng $\ge 0$ không làm đường đi dài ra. Đường đi đơn qua tối đa $N$ đỉnh nên có tối đa $N-1$ cạnh.

Bằng quy nạp: sau vòng thứ $t$, $dist[v]$ không lớn hơn độ dài đường đi ngắn nhất từ nguồn tới $v$ dùng tối đa $t$ cạnh. Giả sử đường tối ưu dùng tối đa $t$ cạnh tới $v$ có cạnh cuối là $u\to v$. Phần tới $u$ dùng tối đa $t-1$ cạnh nên sau vòng $t-1$ đã có $dist[u]$ đủ tốt; trong vòng $t$, khi nới lỏng cạnh $u\to v$, $dist[v]$ cũng đủ tốt. Vậy sau $N-1$ vòng, mọi $dist[v]$ đã tối ưu.

Phát hiện chu trình âm

Nếu có một chu trình âm đi tới được từ nguồn, ta có thể đi vòng quanh nó mãi để khoảng cách giảm tới $-\infty$: bài toán "đường đi ngắn nhất" không còn nghĩa. Dấu hiệu nhận biết rất gọn: chạy thêm vòng thứ $N$ và xem còn cạnh nào nới lỏng được không. Mệnh đề "vòng $N$ còn nới lỏng được $⟺$ có chu trình âm tới được từ nguồn" đúng theo cả hai chiều, nhưng mỗi chiều dựa trên một lý do khác nhau:

• Còn nới lỏng được $\Rightarrow$ có chu trình âm (phản đảo của lập luận $N-1$ vòng). Nếu không có chu trình âm thì sau $N-1$ vòng mọi $dist[v]$ đã bằng đúng khoảng cách ngắn nhất. Mà $dist[v]$ luôn là độ dài của một đường đi thật nào đó nên không thể nhỏ hơn khoảng cách ngắn nhất; vậy vòng $N$ không nới lỏng được cạnh nào. Lật lại: vòng $N$ còn nới lỏng được thì phải có chu trình âm.
• Có chu trình âm $\Rightarrow$ vòng $N$ chắc chắn còn nới lỏng được (lập luận cộng bất đẳng thức). Gọi chu trình âm là $v_0\to v_1\to \dots \to v_k=v_0$; các $dist[v_i]$ đều hữu hạn vì chu trình tới được từ nguồn. Giả sử vòng $N$ không nới lỏng được cạnh nào, tức mọi cạnh trên chu trình đều thỏa $dist[v_{i+1}]\le dist[v_i]+w_i$. Cộng $k$ bất đẳng thức này lại, tổng các $dist$ hai vế triệt tiêu nhau, còn $0\le \sum w_i<0$: vô lý. Vậy phải có ít nhất một cạnh trên chu trình còn nới lỏng được.

Floyd-Warshall: quy hoạch động theo đỉnh trung gian

Gọi $d_k[i][j]$ là độ dài đường đi ngắn nhất từ $i$ tới $j$ mà mọi đỉnh trung gian (không tính hai đầu) đều thuộc tập $\{1,2,\dots ,k\}$. Khi mở rộng tập được phép thêm đỉnh $k$, đường tối ưu mới chỉ có hai khả năng:

• Không đi qua $k$: giữ nguyên $d_{k-1}[i][j]$.
• Đi qua $k$ đúng một lần (không có chu trình âm thì đi qua $k$ hai lần không lợi): tách thành $i⤳k$ và $k⤳j$, mỗi đoạn chỉ dùng trung gian trong $\{1,\dots ,k-1\}$.

$$d_k[i][j]=min(d_{k-1}[i][j],d_{k-1}[i][k]+d_{k-1}[k][j])$$

Cơ sở: $d_0[i][j]$ là trọng số cạnh trực tiếp ($0$ nếu $i=j$, $\infty$ nếu không có cạnh). Đáp án là $d_N$. Có thể dùng một mảng 2 chiều duy nhất thay vì $N+1$ lớp, vì ở bước $k$ hàng $k$ và cột $k$ không đổi: $d[i][k]=min(d[i][k],d[i][k]+d[k][k])$ với $d[k][k]=0$.

Vì sao vòng $k$ phải ở ngoài cùng? Công thức trên yêu cầu khi xét tầng $k$, mọi giá trị $d[i][k]$ và $d[k][j]$ đều đã hoàn tất cho tầng $k-1$. Đặt $k$ ngoài cùng đảm bảo điều đó: xong trọn một tầng rồi mới sang tầng sau. Nếu đặt $k$ ở trong cùng (thứ tự i, j, k), thì $d[i][j]$ chỉ được tính một lần duy nhất, từ các giá trị $d[i][k]$, $d[k][j]$ có thể chưa được tính xong, và kết quả sai (xem ví dụ phản chứng ở phần Lỗi thường gặp).

Ví dụ chạy tay

Bellman-Ford

Đồ thị 4 đỉnh, nguồn là đỉnh 0, có một cạnh âm $1\to 2$. Cố tình liệt kê các cạnh theo thứ tự "xấu" để thấy vì sao cần nhiều vòng:

   (0) --4--> (1) --(-3)--> (2) --2--> (3)
    |          |             ^          ^
    |          +------6------|----------+
    +-----------3------------+

Các cạnh: 0->1 (4), 0->2 (3), 1->2 (-3), 1->3 (6), 2->3 (2)

Thứ tự duyệt cạnh mỗi vòng:
  (2->3, 2)  (1->2, -3)  (1->3, 6)  (0->1, 4)  (0->2, 3)

Theo dõi mảng $dist$ (∞ là chưa tới được):

                 dist[0] dist[1] dist[2] dist[3]
Ban đầu:            0       ∞       ∞       ∞

Vòng 1: 2->3 bỏ qua (dist[2]=∞), 1->2, 1->3 bỏ qua (dist[1]=∞)
        0->1: dist[1] = 0+4 = 4
        0->2: dist[2] = 0+3 = 3
                    0       4       3       ∞

Vòng 2: 2->3: dist[3] = 3+2 = 5
        1->2: dist[2] = 4-3 = 1      <- cạnh âm cho đường tốt hơn
        1->3: 4+6 = 10 > 5, bỏ qua
                    0       4       1       5

Vòng 3: 2->3: dist[3] = 1+2 = 3      <- phải đợi dist[2] tốt lên mới cải thiện được
                    0       4       1       3

Vòng 4 (kiểm tra): không cạnh nào nới lỏng được -> không có chu trình âm.

Đường ngắn nhất tới đỉnh 3 là $0\to 1\to 2\to 3$ gồm 3 cạnh, và đúng là phải tới vòng $3=N-1$ mới tìm ra nó. Dijkstra bản có mảng visited (đỉnh đã chốt thì không bao giờ được cập nhật lại) sẽ sai ở đây: nó lấy đỉnh 2 ra trước (khoảng cách $3<4$), chốt $dist[2]=3$ và gán tạm $dist[3]=3+2=5$. Khi lấy đỉnh 1 ra, đường $0\to 1\to 2$ chỉ tốn $1$, nhưng đỉnh 2 đã bị chốt nên giá trị này không được lan truyền tiếp sang đỉnh 3. Cuối cùng $dist[2]=3$ và $dist[3]=5$ đều sai (đúng là $1$ và $3$). Bản Dijkstra "lazy" (không có visited, chỉ bỏ qua phần tử cũ bằng if (d != dist[u]) continue;) vẫn cho phép một đỉnh được cập nhật và đẩy lại vào hàng đợi, nên có thể vẫn ra đúng trên ví dụ nhỏ này. Tuy nhiên với cạnh âm, mỗi đỉnh có thể bị lấy ra và xử lý lại rất nhiều lần: tồn tại đồ thị khiến bản lazy chạy thời gian mũ. Vì vậy không dùng Dijkstra (bản nào cũng vậy) khi có cạnh âm.

Giờ thêm cạnh $3\to 1$ trọng số $-2$ (duyệt sau cùng trong mỗi vòng). Chu trình $1\to 2\to 3\to 1$ có tổng $-3+2-2=-3<0$:

Vòng 1:  dist = [0, 4, 3, ∞]
Vòng 2:  dist = [0, 3, 1, 5]     (3->1: 5-2 = 3 kéo dist[1] từ 4 xuống 3)
Vòng 3:  dist = [0, 1, 0, 3]     (các giá trị trên chu trình tiếp tục giảm)
Vòng 4:  dist = [0, 0, -2, 2]    <- vòng thứ N VẪN nới lỏng được => có chu trình âm

Code ở phần Cài đặt đánh số đỉnh từ $1$ và lấy nguồn là đỉnh $1$, nên để chạy thử ví dụ trên, cộng $1$ vào mọi số hiệu đỉnh (giữ nguyên thứ tự cạnh "xấu"). Input bên trái in ra 0 4 1 3 (mỗi số một dòng); input bên phải có thêm cạnh 4 2 -2 (tức cạnh $3\to 1$ ở trên) và in ra NEGATIVE CYCLE: 4 2 3 4:

4 5          4 6
3 4 2        3 4 2
2 3 -3       2 3 -3
2 4 6        2 4 6
1 2 4        1 2 4
1 3 3        1 3 3
             4 2 -2

Floyd-Warshall

Đồ thị có hướng 4 đỉnh: $1\to 2$ (4), $1\to 3$ (8), $2\to 3$ (1), $2\to 4$ (7), $3\to 1$ (2), $3\to 4$ (3). Ma trận ban đầu $d_0$:

Lần lượt cho phép từng đỉnh làm trung gian:

k = 1 (được đi qua đỉnh 1):
    d[3][2] = d[3][1] + d[1][2] = 2 + 4 = 6          (∞ -> 6)

k = 2 (được đi qua 1, 2):
    d[1][3] = d[1][2] + d[2][3] = 4 + 1 = 5          (8 -> 5)
    d[1][4] = d[1][2] + d[2][4] = 4 + 7 = 11         (∞ -> 11)

k = 3 (được đi qua 1, 2, 3):
    d[1][4] = d[1][3] + d[3][4] = 5 + 3 = 8          (11 -> 8)
    d[2][1] = d[2][3] + d[3][1] = 1 + 2 = 3          (∞ -> 3)
    d[2][4] = d[2][3] + d[3][4] = 1 + 3 = 4          (7 -> 4)

k = 4: đỉnh 4 không có cạnh ra, không cập nhật gì.

Để ý ở $k=3$: $d[1][4]=8$ dùng giá trị $d[1][3]=5$ vừa được cải thiện ở tầng $k=2$. Đó chính là lý do phải làm xong trọn tầng $k-1$ trước khi sang tầng $k$. Ma trận kết quả (ô đậm là ô đã thay đổi so với ban đầu):

Cài đặt

Bellman-Ford (có truy vết chu trình âm)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;   // chừa biên để cộng không tràn

struct Edge { int u, v; ll w; };

int main() {
    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;   // đỉnh đánh số 1..n

    int src = 1;
    vector<ll> dist(n + 1, INF);
    vector<int> par(n + 1, 0);
    dist[src] = 0;

    int last = -1;   // đỉnh cuối cùng được nới lỏng trong vòng hiện tại
    for (int round = 1; round <= n; round++) {   // n vòng: n-1 vòng chính + 1 vòng kiểm tra
        last = -1;
        for (auto& [u, v, w] : edges) {
            if (dist[u] == INF) continue;          // chưa tới được u: không nới lỏng từ ∞
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                par[v] = u;
                last = v;
            }
        }
        if (last == -1) break;   // một vòng không đổi gì: đã hội tụ, dừng sớm
    }

    if (last == -1) {
        for (int v = 1; v <= n; v++) {
            if (dist[v] == INF) cout << "INF\n";
            else cout << dist[v] << '\n';
        }
    } else {
        // Vòng thứ n vẫn nới lỏng được: có chu trình âm.
        // Lùi n bước theo par để chắc chắn đứng TRÊN chu trình (không phải trên nhánh dẫn vào).
        int x = last;
        for (int i = 0; i < n; i++) x = par[x];
        vector<int> cyc = {x};
        for (int v = par[x]; v != x; v = par[v]) cyc.push_back(v);
        cyc.push_back(x);
        reverse(cyc.begin(), cyc.end());   // par đi ngược, đảo lại cho đúng chiều
        cout << "NEGATIVE CYCLE:";
        for (int v : cyc) cout << ' ' << v;
        cout << '\n';
    }
    return 0;
}

SPFA (Bellman-Ford dùng hàng đợi)

Quan sát: trong một vòng Bellman-Ford, chỉ những cạnh đi ra từ đỉnh vừa được cải thiện ở vòng trước mới có thể nới lỏng thêm. SPFA (Shortest Path Faster Algorithm) giữ một hàng đợi các đỉnh vừa thay đổi và chỉ duyệt cạnh ra của chúng. Chương trình dưới đây đọc cùng định dạng input với code Bellman-Ford ở trên (nên chạy được với hai input mẫu, chỉ in NEGATIVE CYCLE mà không truy vết):

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;

// Trả về false nếu có chu trình âm đi tới được từ src
bool spfa(int src, int n, const vector<vector<pair<int, ll>>>& adj, vector<ll>& dist) {
    dist.assign(n + 1, INF);
    vector<int> cnt(n + 1, 0);        // số cạnh trên đường tốt nhất hiện tại tới v
    vector<char> inQueue(n + 1, 0);
    queue<int> q;
    dist[src] = 0; q.push(src); inQueue[src] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inQueue[u] = 0;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                cnt[v] = cnt[u] + 1;
                if (cnt[v] >= n) return false;   // đường có >= n cạnh thì phải lặp đỉnh: chu trình âm
                if (!inQueue[v]) { q.push(v); inQueue[v] = 1; }
            }
        }
    }
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }
    vector<ll> dist;
    if (!spfa(1, n, adj, dist)) { cout << "NEGATIVE CYCLE\n"; return 0; }
    for (int v = 1; v <= n; v++) {
        if (dist[v] == INF) cout << "INF\n";
        else cout << dist[v] << '\n';
    }
    return 0;
}

⚠️ SPFA không nhanh hơn Bellman-Ford trong trường hợp xấu nhất. Trên dữ liệu ngẫu nhiên nó thường chạy gần $O(E)$, nhưng tồn tại các đồ thị (lưới, đồ thị được dựng riêng để "giết" SPFA) buộc nó chạy đúng $O(VE)$. Nhiều kỳ thi cố ý thêm test như vậy. Tuyệt đối không dùng SPFA thay Dijkstra khi mọi cạnh không âm. Chỉ dùng SPFA khi buộc phải có cạnh âm (ví dụ trong luồng chi phí cực tiểu) và giới hạn cho phép $O(VE)$.

Floyd-Warshall

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> d(n + 1, vector<ll>(n + 1, INF));
    for (int i = 1; i <= n; i++) d[i][i] = 0;
    for (int e = 0; e < m; e++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], w);   // cạnh bội: giữ cạnh rẻ nhất
        // đồ thị vô hướng: thêm d[v][u] = min(d[v][u], w);
    }

    for (int k = 1; k <= n; k++)            // k (đỉnh trung gian) PHẢI ở ngoài cùng
        for (int i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;   // không tới được k thì bỏ qua cả hàng
            for (int j = 1; j <= n; j++)
                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        }

    // Sau khi chạy: d[i][i] < 0 nghĩa là i nằm trên một chu trình âm.
    // Nếu đồ thị có thể có chu trình âm, cần chặn dưới để không tràn số (xem Lỗi thường gặp).
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << (d[a][b] == INF ? -1 : d[a][b]) << '\n';
    }
    return 0;
}

Bản Python (chỉ nên dùng với $n$ cỡ vài trăm; mỗi tầng $k$ cập nhật cả một hàng bằng list comprehension để nhanh hơn ba vòng lặp thuần):

INF = float('inf')

def floyd(d):
    n = len(d)
    for k in range(n):
        dk = d[k]
        for i in range(n):
            dik = d[i][k]
            if dik == INF:
                continue
            # relax the whole row i through k at once
            d[i] = [a if a <= dik + b else dik + b for a, b in zip(d[i], dk)]
    return d

Bao đóng bắc cầu (transitive closure)

Chỉ cần biết "$i$ có tới được $j$ không", thay min/+ bằng or/and: . Với bitset, cả hàng $i$ được "or" với hàng $k$ trong một phép toán, nhanh gấp khoảng 64 lần:

const int MAXN = 2000;
bitset<MAXN> reach[MAXN];   // reach[i][j] = 1 nếu có cạnh i -> j (và reach[i][i] = 1)

void transitiveClosure(int n) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            if (reach[i][k]) reach[i] |= reach[k];   // i tới được k thì tới được mọi đỉnh k tới được
}

Chu trình rẻ nhất qua mỗi đỉnh (đồ thị có hướng)

Mẹo nhỏ: khởi tạo $d[i][i]=\infty$ thay vì $0$. Khi đó $d[i][i]$ không còn là "đứng yên" mà bắt buộc phải đi ít nhất một cạnh và quay về, nên sau Floyd-Warshall $d[i][i]$ chính là chu trình rẻ nhất đi qua $i$ (còn $\infty$ nếu $i$ không nằm trên chu trình nào):

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) d[i][j] = INF;   // kể cả đường chéo
// ... đọc cạnh, chạy Floyd-Warshall như trên ...
// d[i][i] = chi phí chu trình rẻ nhất qua i

Ví dụ với 4 đỉnh và các cạnh $1\to 2$ (2), $2\to 3$ (2), $3\to 1$ (3), $1\to 3$ (1), $3\to 4$ (1): kết quả $d[1][1]=d[3][3]=4$ (chu trình $1\to 3\to 1$), $d[2][2]=7$ (chu trình duy nhất qua 2 là $2\to 3\to 1\to 2$), $d[4][4]=\infty$. Chú ý mỗi đỉnh có đáp án riêng: chu trình rẻ nhất của toàn đồ thị (tốn 4) không đi qua đỉnh 2.

Độ phức tạp

• Bellman-Ford: thời gian $O(VE)$, bộ nhớ $O(V+E)$. Có tối đa $V$ vòng (gồm vòng kiểm tra), mỗi vòng duyệt đủ $E$ cạnh với $O(1)$ mỗi cạnh. Chỉ cần mảng $dist$, $par$ cỡ $V$ và danh sách cạnh cỡ $E$. Bản dừng sớm thường nhanh hơn nhiều trên thực tế nhưng không cải thiện trường hợp xấu nhất.
• SPFA: thời gian trung bình gần $O(E)$, xấu nhất $O(VE)$, bộ nhớ $O(V+E)$. Chia quá trình chạy hàng đợi FIFO thành các pha: pha 1 là nguồn, pha $t+1$ gồm các đỉnh được đẩy vào trong lúc xử lý pha $t$. Pha $t$ tương ứng vòng $t$ của Bellman-Ford (sau pha $t$, $dist$ ít nhất tốt bằng sau vòng $t$), nên khi không có chu trình âm chỉ có tối đa $V-1$ pha có đỉnh bị đổi. Nhờ cờ inQueue, mỗi đỉnh vào hàng đợi tối đa một lần mỗi pha, và mỗi lần lấy ra thì duyệt hết cạnh ra của nó; mỗi pha tốn tối đa $O(E)$, tổng là $O(VE)$, không tốt hơn Bellman-Ford.
• Floyd-Warshall: thời gian $O(V^3)$, bộ nhớ $O(V^2)$. Ba vòng lặp lồng nhau mỗi vòng $V$ lần, thân vòng $O(1)$. Ma trận $d$ cỡ $V\times V$ (nhờ dùng một lớp duy nhất). Với $V=500$: $1.25\times {10}^8$ phép so sánh đơn giản, chạy được trong khoảng 1 giây. Với $V=1000$ đã là ${10}^9$, rất sát giới hạn.
• Bao đóng bắc cầu bằng bitset: $O(V^3/64)$ thời gian, $O(V^2/64)$ bộ nhớ, vì mỗi phép |= xử lý 64 bit cùng lúc.

Khi nào chọn thuật nào?

Quy tắc ngón tay cái: không có cạnh âm thì gần như không bao giờ dùng Bellman-Ford/SPFA. Floyd-Warshall được ưa chuộng khi $V$ nhỏ không phải vì nó nhanh, mà vì nó ngắn, khó cài sai và cho luôn cả ma trận khoảng cách.

⚠️ Lỗi thường gặp

• Đặt sai thứ tự vòng lặp Floyd-Warshall. Triệu chứng: vài cặp đỉnh ra $\infty$ hoặc lớn hơn đáp án, dù code "trông giống hệt". Ví dụ phản chứng: chuỗi $1\to 2\to 4\to 3$, mọi cạnh trọng số 1. Với thứ tự i, j, k, khi tính $d[1][3]$ thì $d[1][4]$ chưa được tính (vì $j=4$ đến sau) và $d[2][3]$ cũng chưa (vì $i=2$ đến sau), nên $d[1][3]$ ra $\infty$ thay vì $3$. Cách tránh: luôn viết for k ở ngoài cùng.

• Cộng với $\infty$ gây tràn số hoặc "nới lỏng giả". Nếu $INF$ = LLONG_MAX thì INF + w tràn thành số âm. Nếu $INF$ vừa phải nhưng có cạnh âm, INF + (-5) < INF khiến đỉnh chưa tới được bị gán khoảng cách "gần vô cực" và lan truyền sai. Cách tránh: dùng INF = LLONG_MAX / 4 và luôn kiểm tra dist[u] != INF (Bellman-Ford) hoặc d[i][k] != INF && d[k][j] != INF (Floyd) trước khi cộng.

• Dùng int cho khoảng cách. Đường đi dài tới $N-1$ cạnh, mỗi cạnh ${10}^9$, tổng vượt xa int. Với chu trình âm, giá trị còn giảm liên tục qua các vòng. Dùng long long.

• Floyd-Warshall trên đồ thị có chu trình âm tràn cả long long. Khi có chu trình âm, $d[i][k]+d[k][j]$ cộng hai số âm với nhau, nên giá trị âm có thể tăng gấp đôi (hoặc hơn) về độ lớn qua mỗi tầng $k$ (giảm theo cấp số mũ), vượt $-2^{63}$ chỉ sau vài chục tầng và tràn thành số dương rác. Mức độ phụ thuộc vào số chu trình âm. Một chu trình âm đơn lẻ trên đồ thị thưa thường chưa tràn: chu trình 200 đỉnh, mọi cạnh $-{10}^9$, giá trị nhỏ nhất sau Floyd chỉ cỡ $-4·{10}^{11}$, vì chỉ có một cách đi vòng nên giá trị giảm tuyến tính. Còn đồ thị dày có rất nhiều chu trình âm thì tràn rất nhanh: đồ thị đầy đủ chỉ 15 đỉnh, mọi cạnh $-{10}^9$, đã tràn ở tầng $k=14$; đồ thị đầy đủ 26 đỉnh với mọi cạnh chỉ $-1$ cũng tràn (ở tầng $k=25$). Cách tránh: nếu đề không loại trừ chu trình âm, chặn dưới sau mỗi lần cộng, hoặc dừng ngay khi thấy một $d[k][k]<0$ nếu chỉ cần biết "có chu trình âm":

  ll nd = d[i][k] + d[k][j];      // cả hai >= -INF nên phép cộng không tràn
  nd = max(nd, -INF);             // chặn dưới: mọi giá trị <= -INF coi là -vô cực
  if (nd < d[i][j]) d[i][j] = nd;
  

• Chỉ phát hiện chu trình âm đi tới được từ nguồn. Bellman-Ford từ đỉnh 1 không "thấy" chu trình âm nằm ở phần đồ thị không tới được từ 1. Nếu đề hỏi "đồ thị có chu trình âm không" (bất kể ở đâu), hãy khởi tạo mọi $dist[v]=0$ (tương đương thêm một nguồn ảo nối tới mọi đỉnh với cạnh trọng số 0).

• Có chu trình âm nhưng không ảnh hưởng đáp án. Ngược lại với lỗi trên: nếu đề hỏi đường ngắn nhất từ $s$ tới $t$, một chu trình âm chỉ làm đáp án thành $-\infty$ khi nó vừa tới được từ $s$ vừa tới được $t$. Đừng in "vô cực" chỉ vì vòng thứ $N$ còn nới lỏng được; hãy kiểm tra thêm đỉnh bị nới lỏng có nằm trên đường $s⤳t$ không (BFS/DFS xuôi từ $s$ và ngược từ $t$).

• Truy vết chu trình âm từ đỉnh chưa nằm trên chu trình. Đỉnh last được nới lỏng ở vòng $N$ có thể chỉ nằm trên nhánh dẫn vào chu trình. Phải lùi theo par đủ $N$ bước trước rồi mới đi vòng để in, nếu không vòng lặp in chu trình có thể không bao giờ quay lại điểm xuất phát.

• Dùng SPFA cho đồ thị trọng số không âm. Code chạy đúng, qua test ví dụ, rồi TLE ở test được dựng riêng. Không có cạnh âm thì dùng Dijkstra.

• Chu trình rẻ nhất trên đồ thị vô hướng. Mẹo $d[i][i]=\infty$ chỉ đúng với đồ thị có hướng. Với đồ thị vô hướng, $d[i][i]$ sẽ bằng $2\times$ cạnh rẻ nhất kề $i$ (đi sang rồi quay lại ngay trên cùng một cạnh), không phải chu trình thật. Xem biến thể ở phần dưới.

• Quên cạnh bội và khuyên. Khi đọc cạnh vào ma trận, phải lấy min với giá trị cũ; gán thẳng d[u][v] = w có thể ghi đè một cạnh rẻ hơn. Khuyên $u\to u$ trọng số âm làm $d[u][u]<0$, tức là chu trình âm một cạnh.

Biến thể / Mở rộng

• Chu trình nhỏ nhất trên đồ thị vô hướng. Chạy Floyd-Warshall, và trước khi cập nhật tầng $k$, thử khép chu trình $i⤳j\to k\to i$ với $i,j<k$. Lúc đó $d[i][j]$ chỉ đi qua các đỉnh $<k$ nên chắc chắn không chứa $k$, chu trình tạo ra là hợp lệ:

  // w[u][v]: trọng số cạnh gốc (INF nếu không có); d khởi tạo bằng w, d[i][i] = 0
  ll best = INF;
  for (int k = 1; k <= n; k++) {
      for (int i = 1; i < k; i++)
          for (int j = i + 1; j < k; j++)
              if (d[i][j] != INF && w[j][k] != INF && w[k][i] != INF)
                  best = min(best, d[i][j] + w[j][k] + w[k][i]);
      // ... sau đó mới cập nhật d theo k như Floyd-Warshall thường ...
  }
  

• Đỉnh bị ảnh hưởng bởi chu trình âm (Floyd). Sau Floyd, $d[i][j]=-\infty$ khi tồn tại $k$ với $d[k][k]<0$, $d[i][k]<\infty$ và $d[k][j]<\infty$. Với Bellman-Ford, đánh dấu các đỉnh bị nới lỏng ở vòng thứ $N$ rồi BFS lan ra mọi đỉnh chúng tới được.

• Floyd biến thể "minimax / maximin". Thay $(min,+)$ bằng $(min,max)$ để tìm đường có cạnh lớn nhất nhỏ nhất (hoặc $(max,min)$ cho "thông lượng" lớn nhất). Cấu trúc ba vòng giữ nguyên vì $(min,max)$ và $(max,min)$ cũng tạo thành semiring giống $(min,+)$ (phép "nối hai đoạn đường" phân phối qua phép "chọn đường tốt hơn"), và đi thêm một chu trình không bao giờ làm cạnh lớn nhất nhỏ đi (hay cạnh nhỏ nhất lớn lên), nên luôn có đường tối ưu là đường đơn: không có khái niệm "chu trình âm" cần lo.

• Đường đi dùng tối đa $K$ cạnh. Bellman-Ford dừng sau đúng $K$ vòng (dùng bản sao dist của vòng trước để mỗi vòng chỉ thêm đúng một cạnh). Với $K$ rất lớn, dùng lũy thừa ma trận theo phép $(min,+)$, xem DP nhân ma trận.

• Johnson: mọi cặp trên đồ thị thưa có cạnh âm. Chạy Bellman-Ford một lần từ nguồn ảo để lấy thế năng $h(v)$, đổi trọng số $w^{\prime }(u,v)=w(u,v)+h(u)-h(v)\ge 0$, rồi chạy Dijkstra từ mỗi đỉnh: $O(VE+V(V+E)\log V)$. Cùng ý tưởng thế năng xuất hiện trong luồng chi phí cực tiểu.

• Hệ ràng buộc hiệu (difference constraints). Hệ bất phương trình $x_v-x_u\le c$ tương ứng cạnh $u\to v$ trọng số $c$; hệ có nghiệm khi và chỉ khi đồ thị không có chu trình âm, và $dist$ từ Bellman-Ford (với nguồn ảo) chính là một nghiệm.

Bài tập luyện

Luyện kỹ thuật

• Đường Đi Ngắn Nhất II (shortroute2) (Trung cấp) Bài Floyd-Warshall thuần: $n\le 500$ và tới ${10}^5$ truy vấn cặp đỉnh, nên tính trước toàn bộ ma trận rồi trả lời $O(1)$. Đường là hai chiều và có thể có cạnh bội: khi đọc cạnh phải gán cả d[u][v] lẫn d[v][u] (bỏ comment dòng tương ứng trong code mẫu) và lấy min với giá trị cũ; dùng long long cho $INF$.
• Phân Phối Quà Tặng (redistgft) (Trung cấp) Dựng đồ thị "bò $i$ thích quà $g$ hơn quà của mình" rồi cần biết ai tới được ai: đúng dạng bao đóng bắc cầu với $N\le 500$.
• Tìm Chu Trình Âm (cyclefind) (Trung cấp) Bellman-Ford chạy $n$ vòng để phát hiện và in ra một chu trình âm bất kỳ; luyện khởi tạo nguồn ảo và truy vết par đúng cách.
• Điểm Số Cao Nhất (highscore) (Trung cấp) Đổi dấu trọng số để biến "lớn nhất" thành "nhỏ nhất", rồi chỉ in $-1$ khi chu trình (dương trước khi đổi dấu) thực sự nằm trên đường từ 1 tới $n$.
• Combo chiến đấu (cowmbat) (Nâng cao) Floyd-Warshall trên bảng chi phí đổi chữ tối đa $26\times 26$ (đổi gián tiếp có thể rẻ hơn đổi trực tiếp), dùng kết quả làm đầu vào cho một bài quy hoạch động trên xâu.

Đề VOI

• Nâng cấp mạng (voi11_ugnet) (Nâng cao) VOI 2011: cần "thông lượng lớn nhất" của đường đi giữa hai đầu mỗi cáp; với subtask $n\le 100$, Floyd-Warshall biến thể $(max,min)$ (mục Biến thể ở trên) tính được giá trị này cho mọi cặp trong $O(n^3)$. Đây chỉ là cách cho subtask nhỏ: lời giải đầy đủ với $n\le {10}^5$ cần cây khung và DSU.
• Hành trình du lịch (voi13_tours) (Nâng cao) VOI 2013: đáp án của mỗi địa điểm là một chu trình rẻ nhất đi qua nó trên đồ thị có hướng; xem mục "Chu trình rẻ nhất qua mỗi đỉnh" ở trên, và chú ý tổng $n$ tới $1000$ nên $O(n^3)$ khá sát giới hạn. Bellman-Ford từ mỗi đỉnh đủ cho các subtask nhỏ, còn Dijkstra từ mỗi đỉnh là hướng an toàn hơn về thời gian ở subtask lớn.