Dijkstra Algorithm

IDijkstra

Giữ $d_v$ là độ dài đường tốt nhất đã biết từ nguồn tới $v$, ban đầu $d_s = 0$, còn lại $\infty$. Nới lỏng cạnh $u \to v$ dài $w$: nếu $d_u + w < d_v$ thì gán $d_v = d_u + w$. Dijkstra lặp: lấy đỉnh chưa chốt có $d$ nhỏ nhất, chốt nó, rồi nới mọi cạnh đi ra.

Vì sao đỉnh có $d$ nhỏ nhất đã đúng? Mọi đường tới nó phải rời tập đã chốt qua một cạnh nào đó tới một đỉnh chưa chốt có $d$ ít nhất bằng nó, và phần đường còn lại có độ dài không âm. Lập luận này hỏng khi có cạnh âm: một đường vòng qua cạnh âm có thể quay lại rẻ hơn.

Cài bằng priority_queue các cặp $(d, v)$ nhỏ nhất trước. Không cần thao tác “giảm khóa”: mỗi lần nới thành công thì đẩy cặp mới, và khi lấy ra một cặp có $d$ lớn hơn $d_v$ hiện tại thì bỏ qua. Mỗi cạnh đẩy tối đa một cặp, nên hàng đợi có $O(m)$ phần tử, tổng $O(m \log m)$.

Độ dài tới $10^9$ và đường tới $10^5$ cạnh cho tổng tới $10^{14}$: dùng ll và $\infty = 10^{18}$.

priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, s});
while (!pq.empty()) {
    ll du = pq.top().first, u = pq.top().second;
    pq.pop();
    if (du > d[u]) continue;
    for (pair<ll, ll> e : g[u])
        if (du + e.second < d[e.first]) {
            d[e.first] = du + e.second;
            pq.push({d[e.first], e.first});
        }
}

Ví dụKhoảng Cách Từ Đỉnh Đầu

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ cạnh dài tới $10^9$ (có khuyên và cạnh lặp). In khoảng cách ngắn nhất từ 1 tới mọi đỉnh.

Lời giải. Dijkstra đúng như khung trên. Khuyên và cạnh lặp không cần xử lý riêng: khuyên không bao giờ nới thành công, cạnh lặp chỉ là thêm một lựa chọn.

Bước 1: hàng đợi ưu tiên nhỏ nhất. pq chứa cặp (khoảng cách, đỉnh), greater làm phần tử nhỏ nhất nằm trên đỉnh. INF = 1e18 lớn hơn mọi khoảng cách thật ($10^5 \cdot 10^9$).

for (ll i = 1; i <= n; i++) d[i] = INF;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
d[1] = 0;
pq.push({0, 1});

Bước 2: lấy ra và nới. C++ không có thao tác “giảm khóa”, nên nới được thì đẩy thêm một cặp mới; cặp cũ vẫn nằm trong hàng, và khi lấy ra mà du > d[u] thì nó đã lỗi thời, bỏ qua. Lần đầu một đỉnh được lấy ra với du == d[u], khoảng cách đó đã cuối cùng: mọi đường khác phải đi qua một đỉnh chưa lấy ra, có nhãn không nhỏ hơn, và cạnh không âm chỉ làm dài thêm.

while (!pq.empty()) {
    ll du = pq.top().first, u = pq.top().second;
    pq.pop();
    if (du > d[u]) continue;
    for (pair<ll, ll> e : g[u])
        if (du + e.second < d[e.first]) {
            d[e.first] = du + e.second;
            pq.push({d[e.first], e.first});
        }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5, INF = 1e18;
ll n, m, d[N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (ll i = 1; i <= n; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    d[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        ll du = pq.top().first, u = pq.top().second;
        pq.pop();
        if (du > d[u]) continue;
        for (pair<ll, ll> e : g[u])
            if (du + e.second < d[e.first]) {
                d[e.first] = du + e.second;
                pq.push({d[e.first], e.first});
            }
    }
    for (ll i = 1; i <= n; i++) cout << d[i] << ' ';
    cout << '\n';
}

ChạyInput5 8
1 2 7
1 3 2
3 2 1
2 4 4
3 4 8
4 5 3
3 5 20
2 5 10

Output0 3 2 7 10

Độ phức tạp: mỗi cạnh đẩy tối đa một cặp: $O(m \log m)$.

Nhiều người quen xóa cặp cũ khỏi set thay vì bỏ qua. Cách đó đúng nhưng chậm hơn:

set chậm hơn khoảng 2,3 lần. Cứ dùng priority_queue và bỏ qua cặp cũ.

IIThông tin phụ

Các cạnh $u \to v$ thỏa $d_u + w = d_v$ tạo thành đồ thị đường ngắn nhất: một DAG, vì $d$ tăng ngặt dọc mỗi cạnh khi $w > 0$. Mọi đường ngắn nhất đều đi trên DAG đó, nên đếm số đường, số cạnh ít nhất hay nhiều nhất trên các đường ngắn nhất là quy hoạch động trên DAG (bài 3.3). Dijkstra lấy đỉnh theo $d$ tăng dần, chính là một thứ tự tô pô của DAG này, nên làm luôn trong lúc nới: nới tốt hơn thì đặt lại thông tin phụ của $v$ theo $u$; nới bằng thì gộp thêm. Chẳng hạn với số đường ngắn nhất cnt và số cạnh ít nhất mn:

ll v = e.first, nd = du + e.second;
if (nd < d[v]) {
    d[v] = nd;
    cnt[v] = cnt[u];
    mn[v] = mn[u] + 1;
    pq.push({nd, v});
} else if (nd == d[v]) {
    cnt[v] = (cnt[v] + cnt[u]) % MOD;
    mn[v] = min(mn[v], mn[u] + 1);
}

Cạnh phải dương để mọi $u$ có $d_u + w = d_v$ đều được lấy ra trước $v$; khi $v$ được lấy ra thì mọi đóng góp đã gộp xong.

IIITrạng thái, nguồn ảo

Mở rộng đỉnh. Khi đường đi có thêm một điều kiện hữu hạn (đã dùng phiếu chưa, đang cầm xe nào, đã qua bao nhiêu cạnh đặc biệt), đỉnh mới là cặp (đỉnh cũ, trạng thái). Một phiếu giảm giá dùng đúng một lần cho hai bản sao của đồ thị: tầng 0 chưa dùng, tầng 1 đã dùng, mỗi cạnh có thêm một bản đi từ tầng 0 lên tầng 1 với giá giảm. Số đỉnh nhân với số trạng thái, thuật toán không đổi.

Nguồn ảo. Câu hỏi “với mọi $i$, giá nhỏ nhất của $a_j + \mathrm{dist}(i, j)$” là Dijkstra từ một đỉnh ảo nối tới mọi $j$ bằng cạnh dài $a_j$, trên đồ thị đảo chiều nếu cạnh có hướng. Không cần thêm đỉnh thật: khởi tạo $d_j = a_j$ và đẩy mọi đỉnh vào hàng đợi.

Ví dụPhiếu Giảm Giá Một Chặng

Đề. Đồ thị có hướng $n \le 10^5$ đỉnh, $m \le 2 \cdot 10^5$ chuyến bay. Phải dùng một phiếu cho đúng một chuyến, chuyến đó chỉ trả $\lfloor c / 2 \rfloor$. Tìm chi phí nhỏ nhất từ 1 tới $n$.

Lời giải. Trạng thái $(v, t)$ với $t$ là đã dùng phiếu chưa. Cạnh $a \to b$ giá $c$ cho ba cạnh: $(a, 0) \to (b, 0)$ giá $c$, $(a, 0) \to (b, 1)$ giá $\lfloor c/2 \rfloor$, $(a, 1) \to (b, 1)$ giá $c$. Dijkstra trên $2n$ trạng thái; đáp án là $d(n, 1)$, vì đề bắt buộc dùng phiếu.

Bước 1: đánh số trạng thái. $(v, t)$ là ô 2 * v + t của một mảng d; đỉnh 1 chưa dùng phiếu là ô 2.

for (ll i = 0; i < 2 * N; i++) d[i] = INF;
d[2] = 0;
pq.push({0, 2});

Bước 2: cạnh sinh tại chỗ. Không cần dựng đồ thị $2n$ đỉnh thật: lấy trạng thái $(u, t)$ ra thì sinh cạnh ngay từ danh sách kề gốc của $u$. Luôn đi được cạnh giá $c$ sang $(v, t)$; nếu chưa dùng phiếu thì thêm lựa chọn giá $\lfloor c/2 \rfloor$ sang $(v, 1)$.

ll u = s / 2, t = s % 2;
for (pair<ll, ll> e : g[u]) {
    ll v = e.first, c = e.second;
    if (du + c < d[2 * v + t]) {
        d[2 * v + t] = du + c;
        pq.push({d[2 * v + t], 2 * v + t});
    }
    if (!t && du + c / 2 < d[2 * v + 1]) {
        d[2 * v + 1] = du + c / 2;
        pq.push({d[2 * v + 1], 2 * v + 1});
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1e5 + 5, INF = 1e18;
ll n, m, d[2 * N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (ll i = 0; i < 2 * N; i++) d[i] = INF;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
    d[2] = 0;
    pq.push({0, 2});
    while (!pq.empty()) {
        ll du = pq.top().first, s = pq.top().second;
        pq.pop();
        if (du > d[s]) continue;
        ll u = s / 2, t = s % 2;
        for (pair<ll, ll> e : g[u]) {
            ll v = e.first, c = e.second;
            if (du + c < d[2 * v + t]) {
                d[2 * v + t] = du + c;
                pq.push({d[2 * v + t], 2 * v + t});
            }
            if (!t && du + c / 2 < d[2 * v + 1]) {
                d[2 * v + 1] = du + c / 2;
                pq.push({d[2 * v + 1], 2 * v + 1});
            }
        }
    }
    cout << d[2 * n + 1] << '\n';
}

ChạyInput4 5
1 2 8
2 4 7
1 3 5
3 4 10
2 3 1

Output10

Độ phức tạp: đồ thị trạng thái có $2n$ đỉnh và $3m$ cạnh: $O(m \log m)$.

IVBFS 0-1

Khi mọi cạnh dài 0 hoặc 1, không cần hàng đợi ưu tiên. Dùng một hàng đợi hai đầu: nới thành công qua cạnh 0 thì đẩy vào đầu, qua cạnh 1 thì đẩy vào cuối. Hàng đợi luôn chứa các đỉnh có $d$ bằng $k$ ở phía trước và $k + 1$ ở phía sau, giống BFS theo lớp, nên lấy ra từ đầu luôn là đỉnh nhỏ nhất. Một đỉnh có thể vào hàng nhiều lần, nhưng như Dijkstra, bỏ qua lần lấy ra cũ. Tổng $O(n + m)$.

Ví dụMê Cung Hai Kiểu Di Chuyển

Đề. Lưới $h, w \le 1000$ có tường. Đi bộ sang ô kề cạnh miễn phí; dịch chuyển tới một ô trống trong hình vuông $5 \times 5$ quanh mình tốn 1 phép. Tìm số phép ít nhất từ ô đầu tới ô đích, hoặc $-1$.

Lời giải. Mỗi ô là một đỉnh; bốn ô kề cạnh nối bằng cạnh 0 (đi bộ), các ô trong hình vuông $5 \times 5$ nối bằng cạnh 1 (dịch chuyển). Trọng số chỉ là 0 hoặc 1 nên dùng BFS 0-1: hàng đợi hai đầu, cạnh 0 đẩy vào đầu, cạnh 1 đẩy vào cuối. Hàng đợi luôn có dạng “các ô khoảng cách $k$, rồi các ô $k + 1$”, nên lấy ra từ đầu luôn là ô nhỏ nhất, như Dijkstra mà không cần heap.

Bước 1: khởi tạo. Lưới đánh số từ 1 nhờ thêm một ký tự đệm; d khởi tạo INF, ô xuất phát 0.

for (ll i = 1; i <= h; i++) {
    cin >> s[i];
    s[i] = " " + s[i];
    for (ll j = 1; j <= w; j++) d[i][j] = INF;
}

Bước 2: đi bộ, cạnh 0. Nới được thì đẩy vào đầu, vì ô đó cùng khoảng cách với ô hiện tại.

for (ll k = 0; k < 4; k++) {
    ll nx = x + dx[k], ny = y + dy[k];
    if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
    if (d[x][y] < d[nx][ny]) {
        d[nx][ny] = d[x][y];
        dq.push_front({nx, ny});
    }
}

Bước 3: dịch chuyển, cạnh 1. Duyệt hình vuông $5 \times 5$ quanh ô, nới được thì đẩy vào cuối.

for (ll nx = x - 2; nx <= x + 2; nx++)
    for (ll ny = y - 2; ny <= y + 2; ny++) {
        if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
        if (d[x][y] + 1 < d[nx][ny]) {
            d[nx][ny] = d[x][y] + 1;
            dq.push_back({nx, ny});
        }
    }

Một ô có thể vào hàng nhiều lần; lần lấy ra thứ hai chỉ nới lại với nhãn đã đúng, không làm sai.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 1005, INF = 1e18;
ll h, w, d[N][N];
ll dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
string s[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll sr, sc, tr, tc;
    cin >> h >> w >> sr >> sc >> tr >> tc;
    for (ll i = 1; i <= h; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
        for (ll j = 1; j <= w; j++) d[i][j] = INF;
    }
    deque<pair<ll, ll>> dq;
    d[sr][sc] = 0;
    dq.push_back({sr, sc});
    while (!dq.empty()) {
        ll x = dq.front().first, y = dq.front().second;
        dq.pop_front();
        for (ll k = 0; k < 4; k++) {
            ll nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
            if (d[x][y] < d[nx][ny]) {
                d[nx][ny] = d[x][y];
                dq.push_front({nx, ny});
            }
        }
        for (ll nx = x - 2; nx <= x + 2; nx++)
            for (ll ny = y - 2; ny <= y + 2; ny++) {
                if (nx < 1 || ny < 1 || nx > h || ny > w || s[nx][ny] == '#') continue;
                if (d[x][y] + 1 < d[nx][ny]) {
                    d[nx][ny] = d[x][y] + 1;
                    dq.push_back({nx, ny});
                }
            }
    }
    cout << (d[tr][tc] == INF ? -1 : d[tr][tc]) << '\n';
}

ChạyInput5 5
1 1
5 5
..#..
..#..
#####
..#..
..#..

Output1

Mỗi ô xét $4 + 24$ hướng: khoảng $3 \cdot 10^7$ bước cho $10^6$ ô.