Bellman-Ford and Floyd-Warshall

IBellman-Ford

Nhắc lại từ bài 3.5.1: gọi $d_v$ là độ dài đường tốt nhất đã biết từ nguồn tới $v$, ban đầu $d_1 = 0$ và các đỉnh khác bằng $\infty$; nới cạnh $u \to v$ dài $w$ là gán $d_v = d_u + w$ khi $d_u + w < d_v$. Dijkstra chốt đỉnh có $d$ nhỏ nhất với lý do mọi đường vòng tới nó đều dài thêm. Khi có cạnh âm, lý do này không còn đúng. Chẳng hạn với ba cạnh $1 \to 2$ dài $2$, $1 \to 3$ dài $5$, $3 \to 2$ dài $-4$, Dijkstra lấy đỉnh $2$ ra trước với $d_2 = 2$, trong khi đường $1 \to 3 \to 2$ chỉ dài $1$.

Bellman-Ford không cố chọn thứ tự đúng. Mỗi lượt, nó nới mọi cạnh của đồ thị theo một thứ tự bất kỳ, và lặp lại $n - 1$ lượt.

for (ll i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;
for (ll it = 1; it < n; it++)
    for (ll i = 1; i <= m; i++)
        if (d[ea[i]] != INF && d[ea[i]] + ew[i] < d[eb[i]]) d[eb[i]] = d[ea[i]] + ew[i];

Độ phức tạp: $O(nm)$, với $n = 2500$, $m = 5000$ cần khoảng $1{,}25 \cdot 10^7$ phép tính.

Ở đây cạnh thứ $i$ đi từ ea[i] tới eb[i], dài ew[i]. Điều kiện d[ea[i]] != INF bảo đảm chỉ nới từ những đỉnh đã tới được từ nguồn; nếu bỏ đi, một cạnh âm nối hai đỉnh chưa tới được sẽ làm $\infty$ giảm thành một số “gần vô cùng”, vừa sai vừa dễ tràn số.

Nếu một lượt không nới được cạnh nào thì các lượt sau cũng không, nên có thể dừng sớm. Trên nhiều đồ thị, cách này làm Bellman-Ford chạy nhanh hơn hẳn $n - 1$ lượt.

Một biến thể quen thuộc là SPFA: thay vì nới mọi cạnh mỗi lượt, chỉ nới cạnh đi ra từ những đỉnh vừa được giảm $d$, giữ các đỉnh đó trong một hàng đợi. SPFA thường chạy nhanh, nhưng vẫn có những đồ thị làm nó tốn đúng $O(nm)$, và người ra đề hay cố ý đưa vào loại test đó. Khi mọi cạnh không âm, hãy dùng Dijkstra.

Ví dụĐiểm Số Trên Hành Trình

Đề. Đồ thị có hướng $n \le 2500$ đỉnh, $m \le 5000$ cạnh, mỗi cạnh mang một số điểm từ $-10^9$ tới $10^9$. Đi từ $1$ tới $n$, được đi lại các cạnh bao nhiêu lần cũng được; tìm tổng điểm lớn nhất, hoặc in $-1$ nếu tổng điểm có thể lớn tùy ý.

Lời giải. Bài hỏi lớn nhất, nên ta nới theo chiều tăng: gán $d_v = d_u + w$ khi $d_u + w > d_v$, với $d$ ban đầu là “âm vô cùng”. Khi đó vai trò của chu trình âm thuộc về chu trình có tổng dương.

Cần cẩn thận ở chỗ: một chu trình dương chỉ làm đáp án vô hạn khi nó vừa tới được từ $1$, vừa đi tiếp tới được $n$. Sau $n - 1$ lượt, nếu cạnh $a \to b$ còn làm $d_b$ tăng được thì $b$ đứng sau một chu trình dương tới được từ $1$. Ta chỉ in $-1$ khi thêm $b$ tới được $n$; điều này kiểm bằng một lượt BFS (bài 3.1) từ $n$ trên đồ thị đảo chiều mọi cạnh, đánh dấu các đỉnh tới được $n$.

Hằng “âm vô cùng” chọn là $-4 \cdot 10^{18}$: các tổng thật nằm trong khoảng $\pm 2{,}5 \cdot 10^{12}$, và vì chỉ nới từ đỉnh đã có giá trị, ta không bao giờ cộng thêm vào chính hằng này.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2505, M = 5005, NEG = -4e18;
ll n, m, ea[M], eb[M], ew[M], d[N], ok[N];
vector<ll> rg[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> ea[i] >> eb[i] >> ew[i];
        rg[eb[i]].push_back(ea[i]);
    }
    queue<ll> q;
    q.push(n);
    ok[n] = 1;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        for (ll v : rg[u])
            if (!ok[v]) {
                ok[v] = 1;
                q.push(v);
            }
    }
    for (ll i = 1; i <= n; i++) d[i] = NEG;
    d[1] = 0;
    for (ll it = 1; it < n; it++)
        for (ll i = 1; i <= m; i++)
            if (d[ea[i]] != NEG) d[eb[i]] = max(d[eb[i]], d[ea[i]] + ew[i]);
    for (ll i = 1; i <= m; i++)
        if (d[ea[i]] != NEG && d[ea[i]] + ew[i] > d[eb[i]] && ok[eb[i]]) {
            cout << -1 << '\n';
            return 0;
        }
    cout << d[n] << '\n';
}

ChạyInput4 5
1 2 4
2 4 -1
1 3 -2
3 4 8
2 3 1

Output13

Độ phức tạp: $O(nm)$, với $n = 2500$, $m = 5000$ cần khoảng $1{,}25 \cdot 10^7$ phép tính.

IIPhát hiện và in chu trình âm

Khi đồ thị có chu trình âm tới được từ nguồn, đi vòng quanh nó mãi thì đường càng ngắn, nên “đường đi ngắn nhất” không tồn tại. Theo ô chứng minh ở mục trên, nếu không có chu trình như vậy thì sau $n - 1$ lượt không còn cạnh nào nới được. Vì vậy chỉ cần chạy thêm lượt thứ $n$: còn nới được cạnh nào thì có chu trình âm tới được từ nguồn.

Muốn biết đồ thị có chu trình âm ở bất kỳ đâu, kể cả nơi không tới được từ đỉnh $1$, ta cho mọi $d_v = 0$ ngay từ đầu. Việc này giống thêm một đỉnh ảo nối tới mọi đỉnh bằng cạnh dài $0$ rồi lấy nó làm nguồn.

Ví dụChu Trình Giảm Thời Gian

Đề. Có $T \le 20$ bộ dữ liệu, mỗi bộ là một đồ thị có hướng $n \le 1000$ đỉnh đánh số từ $0$, $m \le 2000$ cạnh, trọng số từ $-1000$ tới $1000$. Cho biết từ đỉnh $0$ có đi tới được một chu trình có tổng âm hay không.

Lời giải. Chạy Bellman-Ford từ đỉnh $0$, $n - 1$ lượt, rồi kiểm lượt thứ $n$. Chỉ nới từ các đỉnh đã tới được, nên chu trình âm nằm ở phần không tới được từ $0$ không làm sai kết quả, đúng như đề yêu cầu.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1005, M = 2005, INF = 1e18;
ll t, n, m, ea[M], eb[M], ew[M], d[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (ll i = 1; i <= m; i++) cin >> ea[i] >> eb[i] >> ew[i];
        for (ll i = 0; i < n; i++) d[i] = INF;
        d[0] = 0;
        for (ll it = 1; it < n; it++)
            for (ll i = 1; i <= m; i++)
                if (d[ea[i]] != INF && d[ea[i]] + ew[i] < d[eb[i]]) d[eb[i]] = d[ea[i]] + ew[i];
        bool neg = false;
        for (ll i = 1; i <= m; i++)
            if (d[ea[i]] != INF && d[ea[i]] + ew[i] < d[eb[i]]) neg = true;
        cout << (neg ? "possible" : "not possible") << '\n';
    }
}

ChạyInput1
4 4
0 1 5
1 2 2
2 1 -4
2 3 7

Outputpossible

Độ phức tạp: $O(nm)$ cho mỗi bộ dữ liệu, với $n = 1000$, $m = 2000$ cần khoảng $2 \cdot 10^6$ phép tính.

Nhiều bài còn yêu cầu in ra một chu trình âm. Ta lưu thêm mảng cha: mỗi lần nới cạnh $u \to v$ thành công thì ghi $par_v = u$. Gọi $x$ là đỉnh được nới ở lượt thứ $n$. Đỉnh $x$ chưa chắc nằm trên chu trình âm, nhưng nó nằm sau chu trình đó trên đường cha. Đi ngược theo cha đúng $n$ bước từ $x$ thì chắc chắn đã đi vào trong chu trình, vì đường cha không thể dài hơn $n$ đỉnh mà không lặp. Từ đỉnh vừa tới, đi theo cha cho tới khi gặp lại nó, ta được cả chu trình theo chiều ngược.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2505, M = 5005;
ll n, m, ea[M], eb[M], ew[M], d[N], par[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) cin >> ea[i] >> eb[i] >> ew[i];
    ll x = 0;
    for (ll it = 1; it <= n; it++) {
        x = 0;
        for (ll i = 1; i <= m; i++)
            if (d[ea[i]] + ew[i] < d[eb[i]]) {
                d[eb[i]] = d[ea[i]] + ew[i];
                par[eb[i]] = ea[i];
                x = eb[i];
            }
    }
    if (!x) {
        cout << "NO\n";
        return 0;
    }
    for (ll i = 1; i <= n; i++) x = par[x];
    vector<ll> cyc;
    cyc.push_back(x);
    for (ll v = par[x]; v != x; v = par[v]) cyc.push_back(v);
    cyc.push_back(x);
    reverse(cyc.begin(), cyc.end());
    cout << "YES\n";
    for (ll i = 0; i < (ll)cyc.size(); i++) cout << cyc[i] << (i + 1 == (ll)cyc.size() ? '\n' : ' ');
}

ChạyInput4 5
1 2 1
2 3 1
3 4 1
4 2 -3
3 1 2

OutputYES
3 4 2 3

Độ phức tạp: $O(nm)$ cho $n$ lượt nới, phần lần theo cha chỉ $O(n)$; với $n = 2500$, $m = 5000$ cần khoảng $1{,}25 \cdot 10^7$ phép tính.

Ở chương trình này mọi $d_v$ bắt đầu bằng $0$, như đã nói, nên chu trình âm ở đâu cũng được tìm thấy.

IIIFloyd-Warshall

Khi $n$ cỡ vài trăm và cần khoảng cách giữa mọi cặp đỉnh, Floyd-Warshall ngắn gọn nhất. Ban đầu $d_{ij}$ là độ dài cạnh trực tiếp ngắn nhất từ $i$ tới $j$ (không có thì $\infty$), và $d_{ii} = 0$. Lần lượt với mỗi $k$ từ $1$ tới $n$, ta thử đi vòng qua $k$:

Sau khi xét xong $k$, $d_{ij}$ là độ dài đường ngắn nhất từ $i$ tới $j$ mà các đỉnh nằm giữa đường chỉ thuộc $\{1, 2, \dots, k\}$. Vì vậy vòng lặp theo $k$ phải nằm ngoài cùng: khi xét $k$, các giá trị $d_{ik}$ và $d_{kj}$ cần đã tính xong với mọi đỉnh trung gian nhỏ hơn $k$. Thuật toán vẫn đúng khi có cạnh âm; nếu có chu trình âm thì sẽ có một $d_{ii}$ nhỏ hơn $0$.

Ví dụBảng Khoảng Cách

Đề. Đồ thị vô hướng $n \le 500$ đỉnh, có thể có cạnh lặp và khuyên, cùng $q \le 10^5$ câu hỏi khoảng cách giữa hai đỉnh; không có đường thì in $-1$.

Lời giải. Số đỉnh nhỏ còn câu hỏi rất nhiều, nên tính khoảng cách mọi cặp một lần bằng Floyd-Warshall rồi mỗi câu hỏi chỉ tra bảng. Có cạnh lặp nên chỉ giữ cạnh ngắn nhất giữa mỗi cặp; đồ thị vô hướng nên ghi cả hai chiều. Trong vòng lặp, khi $d_{ik} = \infty$ thì bỏ qua cả hàng $i$: vừa tránh phép cộng $\infty + \infty$ làm tràn số, vừa nhanh hơn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 505, INF = 1e18;
ll n, m, q, d[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) d[i][j] = (i == j ? 0 : INF);
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
        d[b][a] = min(d[b][a], c);
    }
    for (ll k = 1; k <= n; k++)
        for (ll i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;
            for (ll j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    while (q--) {
        ll a, b;
        cin >> a >> b;
        cout << (d[a][b] == INF ? -1 : d[a][b]) << '\n';
    }
}

+12 dòngChạyInput5 5 6
1 2 8
1 2 3
2 3 4
3 4 2
1 4 20
1 4
4 1
1 5
5 5
2 4
1 2

Output9
9
-1
0
6
3

Độ phức tạp: $O(n^3 + q)$, với $n = 500$ cần khoảng $1{,}25 \cdot 10^8$ phép tính, mỗi câu hỏi $O(1)$.

Thứ tự hai vòng trong cũng ảnh hưởng tới tốc độ, vì các ô d[i][j] với cùng $i$ nằm liền nhau trong bộ nhớ:

Để $j$ ở vòng trong cùng nhanh hơn khoảng 1,7 lần.

Cùng ba vòng lặp còn trả lời được câu hỏi “từ $i$ có đi tới được $j$ không” cho mọi cặp, gọi là bao đóng bắc cầu (transitive closure): thay phép cộng và $\min$ bằng phép “và”, “hoặc” trên giá trị đúng sai, r[i][j] = r[i][j] || (r[i][k] && r[k][j]). Khi mỗi hàng là một bitset (bài 2.7), cả hàng $j$ được xử lý cùng lúc và thuật toán nhanh lên khoảng 64 lần.

IVChu trình nhỏ nhất

Bài toán: cho đồ thị vô hướng có trọng số dương, tìm chu trình có tổng trọng số nhỏ nhất (chu trình có ít nhất ba đỉnh, không đi lại cạnh). Ta chỉ cần sửa Floyd-Warshall một chút.

Xét một chu trình nhỏ nhất và gọi $k$ là đỉnh có số hiệu lớn nhất trên đó; hai đỉnh kề $k$ trên chu trình là $i$ và $j$. Phần còn lại của chu trình là một đường từ $i$ tới $j$ chỉ đi qua các đỉnh nhỏ hơn $k$. Đúng lúc chuẩn bị xét $k$ trong Floyd-Warshall, $d_{ij}$ chính là độ dài đường ngắn nhất như vậy. Vì thế, trước khi dùng $k$ làm đỉnh trung gian, ta thử mọi cặp $i < j < k$ có cạnh tới $k$:

với $w$ là trọng số cạnh trực tiếp (không có cạnh thì $\infty$).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 105, INF = 1e18;
ll n, m, w[N][N], d[N][N];

signed main() {
    cin >> n >> m;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) w[i][j] = (i == j ? 0 : INF);
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        w[a][b] = w[b][a] = min(w[a][b], c);
    }
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) d[i][j] = w[i][j];
    ll ans = INF;
    for (ll k = 1; k <= n; k++) {
        for (ll i = 1; i < k; i++)
            for (ll j = i + 1; j < k; j++)
                if (d[i][j] != INF && w[j][k] != INF && w[k][i] != INF) ans = min(ans, d[i][j] + w[j][k] + w[k][i]);
        for (ll i = 1; i <= n; i++)
            for (ll j = 1; j <= n; j++)
                if (d[i][k] != INF && d[k][j] != INF) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
    if (ans == INF) cout << "No solution\n";
    else cout << ans << '\n';
}

ChạyInput4 5
1 2 1
2 3 1
3 1 5
3 4 1
4 1 1

Output4

Độ phức tạp: $O(n^3)$, với $n = 100$ cần khoảng $2 \cdot 10^6$ phép tính.

Với dãy cạnh trên, chu trình $1 \to 2 \to 3 \to 4 \to 1$ dài $4$, ngắn hơn chu trình $1 \to 2 \to 3 \to 1$ dài $7$. Khi đồ thị không có trọng số, chạy BFS (bài 3.1) từ mỗi đỉnh cũng tìm được chu trình ngắn nhất trong $O(nm)$.

VHệ điều kiện hiệu

Một lớp bài nhìn bề ngoài không giống đồ thị: tìm các số nguyên $x_1, \dots, x_n$ thỏa $m$ điều kiện, mỗi điều kiện có dạng $x_v - x_u \le w$. Hệ như vậy gọi là hệ ràng buộc hiệu (difference constraints).

Hãy để ý rằng điều kiện $x_v \le x_u + w$ giống hệt tính chất của khoảng cách ngắn nhất sau khi không còn nới được: $d_v \le d_u + w$ với mọi cạnh $u \to v$ dài $w$. Vì vậy ta dựng mỗi điều kiện thành một cạnh $u \to v$ dài $w$, thêm một đỉnh ảo nối tới mọi đỉnh bằng cạnh dài $0$, và chạy Bellman-Ford từ đỉnh ảo. Nếu có chu trình âm thì hệ vô nghiệm: cộng các điều kiện dọc chu trình, vế trái triệt tiêu còn $0 \le$ một số âm. Nếu không, $x_v = d_v$ là một nghiệm.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1005, M = 5005;
ll n, m, ea[M], eb[M], ew[M], d[N];

signed main() {
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) cin >> ea[i] >> eb[i] >> ew[i];
    for (ll it = 1; it <= n; it++)
        for (ll i = 1; i <= m; i++)
            if (d[ea[i]] + ew[i] < d[eb[i]]) d[eb[i]] = d[ea[i]] + ew[i];
    for (ll i = 1; i <= m; i++)
        if (d[ea[i]] + ew[i] < d[eb[i]]) {
            cout << "NO\n";
            return 0;
        }
    for (ll i = 1; i <= n; i++) cout << d[i] << (i == n ? '\n' : ' ');
}

ChạyInput3 3
1 2 3
2 3 -2
3 1 -1

Output-3 0 -2

Độ phức tạp: $O(nm)$, với $n = 1000$, $m = 5000$ cần khoảng $5 \cdot 10^6$ phép tính.

Mỗi dòng u v w của input là điều kiện $x_v - x_u \le w$. Cho mọi $d_v = 0$ từ đầu chính là đi trước một lượt từ đỉnh ảo. Nghiệm in ra thỏa cả ba điều kiện: $0 - (-3) \le 3$, $-2 - 0 \le -2$, $-3 - (-2) \le -1$. Điều kiện dạng $x_v - x_u \ge w$ thì đổi thành $x_u - x_v \le -w$ trước khi dựng cạnh.