Dijkstra (Đường đi ngắn nhất)

Dijkstra là thuật toán tìm đường đi ngắn nhất từ một đỉnh nguồn tới mọi đỉnh khác trên đồ thị có trọng số cạnh không âm. Cài bằng hàng đợi ưu tiên (priority queue), thuật toán chạy trong $O((V+E)\log V)$, trong khi cách "cứ cập nhật đến khi hết thay đổi" như Bellman-Ford mất $O(VE)$. Đây là thuật toán đường đi ngắn nhất được dùng nhiều nhất trong thi đấu, và cũng là nền cho rất nhiều kỹ thuật: truy vết, đa nguồn, đồ thị trạng thái mở rộng, đếm số đường đi ngắn nhất, dựng DAG đường đi ngắn nhất.

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

Hình dung ta đổ nước vào đỉnh nguồn $s$ và nước chảy dọc các cạnh với tốc độ đều: cạnh dài $w$ thì mất $w$ đơn vị thời gian. Đỉnh nào bị nước chạm tới sớm nhất thì thời điểm đó chính là khoảng cách ngắn nhất tới nó. Dijkstra mô phỏng đúng quá trình này: luôn xử lý đỉnh gần nguồn nhất trong số các đỉnh chưa xử lý.

Thuật toán giữ mảng $dist[v]$ là độ dài đường đi tốt nhất đã biết tới $v$ (ban đầu $dist[s]=0$, còn lại $\infty$), và lặp:

1. Lấy ra đỉnh $u$ chưa chốt có $dist[u]$ nhỏ nhất. Chốt $u$: $dist[u]$ từ giờ là đáp án cuối cùng.
2. Nới lỏng (relax) mọi cạnh $u\to v$ trọng số $w$: nếu $dist[u]+w<dist[v]$ thì gán $dist[v]=dist[u]+w$.

Vì sao đỉnh lấy ra đã có khoảng cách đúng?

Chứng minh bằng quy nạp theo thứ tự chốt: giả sử mọi đỉnh đã chốt trước đó đều có $dist$ bằng đúng khoảng cách ngắn nhất. Đỉnh chốt đầu tiên là $u=s$ với $dist[s]=0$, hiển nhiên đúng vì mọi trọng số không âm.

Giả sử $u\ne s$ vừa được lấy ra với giá trị $d=dist[u]$ nhỏ nhất trong các đỉnh chưa chốt. Xét một đường đi bất kỳ $P$ từ $s$ tới $u$. Đi dọc $P$ từ $s$, gọi $y$ là đỉnh đầu tiên chưa chốt trên $P$ và $x$ là đỉnh (đã chốt) ngay trước nó. Vì $x$ đã chốt trước nên theo giả thiết quy nạp, $dist[x]$ là khoảng cách đúng, do đó không vượt $\text{len}(P_{s\to x})$. Khi chốt $x$ ta đã nới lỏng cạnh $x\to y$, nên $dist[y]\le dist[x]+w(x,y)\le \text{len}(P_{s\to x})+w(x,y)=\text{len}(P_{s\to y})$. Vì $u$ được chọn là nhỏ nhất, $d\le dist[y]$. Phần còn lại của $P$ (từ $y$ tới $u$) có độ dài $\ge 0$ vì mọi trọng số không âm. Vậy:

$$d\le dist[y]\le \text{len}(P_{s\to y})\le \text{len}(P_{s\to y})+\text{len}(P_{y\to u})=\text{len}(P).$$

Không đường nào tới $u$ ngắn hơn $d$, nên $d$ là khoảng cách ngắn nhất. Hệ quả quan trọng: các đỉnh được chốt theo thứ tự khoảng cách không giảm.

Chỗ duy nhất dùng giả thiết "trọng số không âm" là bất đẳng thức cuối. Nếu có cạnh âm, đoạn $y\to u$ có thể làm đường đi ngắn lại, và một đỉnh đã chốt có thể còn được cải thiện: Dijkstra sai. Khi đó phải dùng Bellman-Ford.

Hàng đợi ưu tiên và "lazy deletion"

Để lấy nhanh đỉnh có $dist$ nhỏ nhất, ta dùng priority_queue chứa các cặp $(dist,\text{đỉnh})$. std::priority_queue không hỗ trợ "giảm khóa" của phần tử đã nằm trong hàng đợi, nên mỗi lần $dist[v]$ giảm ta đẩy thêm một bản ghi mới $(dist[v],v)$ và để bản cũ nằm lại. Khi lấy ra một bản ghi $(d,u)$ mà $d\ne dist[u]$ thì đó là bản ghi cũ (đỉnh $u$ đã được chốt với giá trị nhỏ hơn), chỉ cần bỏ qua. Cách này gọi là lazy deletion (xóa lười).

Ví dụ chạy tay

Đồ thị vô hướng 5 đỉnh, nguồn $s=1$:

            4
     (1)---------(2)
      |         / |
    1 |    2 /    | 1
      |   /       |
     (3)---------(4)---------(5)
            5            3

Cạnh: 1-2:4   1-3:1   3-2:2   2-4:1   3-4:5   4-5:3

Ký hiệu: pq là hàng đợi ưu tiên (phần tử nhỏ nhất ở đầu), * đánh dấu đỉnh đã chốt, par[v] là đỉnh đứng trước $v$ trên đường tốt nhất hiện biết.

Khởi tạo: dist = [ 0,  ∞,  ∞,  ∞,  ∞ ]      (đỉnh 1..5)
          pq   = { (0,1) }

Lấy (0,1): chốt 1*.  Nới 1->2: 0+4=4 < ∞  => dist[2]=4, par[2]=1
                     Nới 1->3: 0+1=1 < ∞  => dist[3]=1, par[3]=1
          dist = [ 0*, 4,  1,  ∞,  ∞ ]
          pq   = { (1,3), (4,2) }

Lấy (1,3): chốt 3*.  Nới 3->2: 1+2=3 < 4  => dist[2]=3, par[2]=3   (đường vòng qua 3 rẻ hơn!)
                     Nới 3->4: 1+5=6 < ∞  => dist[4]=6, par[4]=3
          dist = [ 0*, 3,  1*, 6,  ∞ ]
          pq   = { (3,2), (4,2), (6,4) }         <- (4,2) giờ đã là bản ghi cũ

Lấy (3,2): chốt 2*.  Nới 2->4: 3+1=4 < 6  => dist[4]=4, par[4]=2
          dist = [ 0*, 3*, 1*, 4,  ∞ ]
          pq   = { (4,2), (4,4), (6,4) }

Lấy (4,2): 4 != dist[2]=3  => BẢN GHI CŨ, bỏ qua.

Lấy (4,4): chốt 4*.  Nới 4->5: 4+3=7 < ∞  => dist[5]=7, par[5]=4
          dist = [ 0*, 3*, 1*, 4*, 7 ]
          pq   = { (6,4), (7,5) }

Lấy (6,4): 6 != dist[4]=4  => bản ghi cũ, bỏ qua.
Lấy (7,5): chốt 5*.  Không cải thiện được gì.  pq rỗng => dừng.

Kết quả: dist = [0, 3, 1, 4, 7]
Truy vết 5: 5 <- par 4 <- par 2 <- par 3 <- par 1   =>  1 -> 3 -> 2 -> 4 -> 5  (dài 1+2+1+3 = 7)

Hai điều cần để ý. Thứ nhất, các đỉnh được chốt theo thứ tự $0,1,3,4,7$: không giảm, đúng như chứng minh. Thứ hai, đỉnh $2$ và $4$ đều từng bị đẩy vào pq hai lần; bản ghi thứ hai của mỗi đỉnh bị bỏ qua nhờ phép so sánh d != dist[u].

Cài đặt

C++: Dijkstra + truy vết

Đọc đồ thị vô hướng $n$ đỉnh, $m$ cạnh; in khoảng cách ngắn nhất từ $1$ tới $n$ và một đường đi đạt được (hoặc $-1$).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;   // leave room so INF + w never overflows

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, ll>>> adj(n + 1);   // adj[u] = {v, w}
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});               // remove for directed graphs
    }

    int s = 1, t = n;
    vector<ll> dist(n + 1, INF);
    vector<int> par(n + 1, 0);                  // par[v] = previous vertex on the shortest path
    // min-heap of {distance, vertex}
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;             // stale entry: u was already settled with a smaller d
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {              // relax edge u -> v
                dist[v] = d + w;
                par[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    if (dist[t] == INF) { cout << -1 << '\n'; return 0; }
    vector<int> path;
    for (int v = t; v != 0; v = par[v]) path.push_back(v);  // walk back via par[]
    reverse(path.begin(), path.end());
    cout << dist[t] << '\n';
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

Truy vết chạy được vì par[s] không bao giờ bị gán (với trọng số không âm, $dist[s]=0$ không thể giảm), nên vòng lặp dừng khi gặp par[s] = 0.

Python

import heapq

def dijkstra(n, adj, s):
    """adj[u] = list of (v, w); returns (dist, par)."""
    INF = float("inf")
    dist = [INF] * (n + 1)
    par = [0] * (n + 1)
    dist[s] = 0
    pq = [(0, s)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:          # stale entry
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                par[v] = u
                heapq.heappush(pq, (dist[v], v))
    return dist, par

heapq của Python là min-heap sẵn nên không cần đảo dấu. Với $V,E~{10}^5$ bản Python vẫn chạy được nhưng khá sát giới hạn thời gian; nên đọc input bằng sys.stdin.

Độ phức tạp

• Thời gian: $O((V+E)\log V)$. Mỗi đỉnh được chốt (duyệt danh sách kề) đúng một lần nhờ bước bỏ bản ghi cũ, nên tổng số lần duyệt cạnh là $O(E)$. Mỗi lần nới lỏng thành công đẩy tối đa một bản ghi, nên pq chứa tổng cộng $\le$ (số cung) $+1$ bản ghi, tức $O(E)$ (đồ thị vô hướng như code mẫu lưu mỗi cạnh thành 2 cung, nên cận là $2E+1$); mỗi thao tác push/pop tốn $O(\log E)$, mà với đồ thị đơn thì $E\le V^2$ nên $\log E\le \log V^2=2\log V$. Tổng: $O((V+E)\log V)$. (Nếu có nhiều cạnh song song, cận chính xác là $O((V+E)\log E)$.)
• Bộ nhớ: $O(V+E)$. Danh sách kề $O(V+E)$, mảng $dist$ và $par$ là $O(V)$, hàng đợi có thể chứa tới $O(E)$ bản ghi (vì lazy deletion).

Với đồ thị dày ($E\approx V^2$), bản không dùng heap nhanh hơn: mỗi vòng quét tuyến tính tìm đỉnh chưa chốt có $dist$ nhỏ nhất, tổng $O(V^2)$, không có thừa số $\log$.

So sánh các thuật toán đường đi ngắn nhất:

BFS và 0-1 BFS thực chất là Dijkstra khi hàng đợi ưu tiên "suy biến" thành hàng đợi thường/deque vì chỉ có một hoặc hai mức khoảng cách.

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

• Quên greater<>, heap thành max-heap. priority_queue mặc định lấy phần tử lớn nhất trước. Với bản lazy deletion (d != dist[u]) như trên, kết quả vẫn đúng nhưng số lần duyệt có thể bùng nổ (tới hàm mũ, TLE); với bản dùng mảng visited thì ra đáp án sai. Luôn khai báo greater<pair<ll,int>>, hoặc đẩy {-dist, v} rồi đổi dấu khi lấy ra (và nhớ đổi dấu cả d khi so sánh).
• Đặt sai thứ tự trong cặp. Phải là {khoảng cách, đỉnh}, không phải {đỉnh, khoảng cách}: cặp được so sánh theo thành phần đầu tiên trước.
• Bỏ bước kiểm tra bản ghi cũ. Không có if (d != dist[u]) continue; thì một đỉnh bị duyệt danh sách kề nhiều lần. Khoảng cách vẫn đúng: bản ghi cũ có $d>dist[u]$, mà khi chốt $u$ ta đã nới mọi cạnh của nó, nên $d+w>dist[u]+w\ge dist[v]$ và không nới lỏng nào thành công (vì cùng lý do, số đường đếm bằng nd = d + w cũng vẫn đúng). Cái giá là độ phức tạp có thể phình tới $O(VE)$ (TLE trên đồ thị dày). Tệ hơn, nếu vừa bỏ kiểm tra vừa nới lỏng bằng dist[u] + w thay vì d + w (một cách viết khá phổ biến), bản ghi cũ sẽ cho nd == dist[v] và cộng cnt[u] thêm một lần nữa: số đường đếm được bị sai.
• Tràn số và chọn INF. Tổng trọng số có thể tới ${10}^5\times {10}^9={10}^{14}$: dùng long long cho $dist$ và cho d + w. Chọn INF = LLONG_MAX / 4 thay vì LLONG_MAX để INF + w không tràn thành số âm (khi đó mọi so sánh < đều hỏng).
• Áp dụng khi có cạnh âm. Ví dụ đồ thị có hướng: $1\to 2$ dài $2$, $1\to 3$ dài $3$, $3\to 2$ dài $-2$, $2\to 4$ dài $1$. Dijkstra chốt đỉnh $2$ với $dist=2$ và nới $2\to 4$ thành $dist[4]=3$, trước khi biết đường $1\to 3\to 2$ dài $1$. Bản dùng mảng "đã chốt" (visited) vẫn gán $dist[2]=1$ khi xét $3\to 2$ nhưng không xử lý lại đỉnh $2$, nên $dist[4]$ kẹt ở $3$ trong khi đáp án đúng là $2$: sai mà không báo lỗi (chỗ sai nằm ở $dist[4]$, không phải $dist[2]$). Bản lazy deletion lấy lại bản ghi $(1,2)$ nên ở ví dụ này tự "sửa" được $dist[4]=2$, nhưng nói chung mất hết đảm bảo độ phức tạp (có đồ thị làm nó chạy hàm mũ), và nếu tới được một chu trình âm thì nó nới lỏng mãi không dừng, lặp vô hạn. Gặp cạnh âm, dùng Bellman-Ford.
• Nhầm chiều trên đồ thị có hướng. Muốn "khoảng cách từ mọi đỉnh tới $t$", phải chạy Dijkstra từ $t$ trên đồ thị ngược (đảo chiều mọi cạnh), không phải trên đồ thị gốc.
• Chạy Dijkstra $K$ lần khi chỉ cần một lần đa nguồn. Câu hỏi "khoảng cách từ mỗi đỉnh tới đỉnh đặc biệt gần nhất" chỉ cần một lần Dijkstra với tất cả đỉnh đặc biệt làm nguồn (xem bên dưới), không phải $K$ lần.
• Đếm số đường đi khi có cạnh trọng số 0. Công thức đếm ở dưới dựa vào việc mọi "đỉnh trước" của $v$ đều được chốt trước $v$. Cạnh 0 phá vỡ điều này (và chu trình 0 còn cho vô số đường ngắn nhất). Khi có cạnh 0, phải xử lý riêng (vd sắp topo trong từng lớp cùng khoảng cách).

Biến thể / Mở rộng

Dijkstra đa nguồn (multi-source)

Bài toán: có một tập nguồn $S$ (các trạm sạc, các bệnh viện...), cần $dist[v]={min}_{s\in S}d(s,v)$. Chỉ cần đẩy tất cả nguồn vào hàng đợi với khoảng cách 0 rồi chạy như bình thường. Nó tương đương thêm một nút nguồn ảo $S^{*}$ nối tới mọi $s\in S$ bằng cạnh trọng số 0.

vector<ll> multiSource(int n, const vector<vector<pair<int, ll>>>& adj, const vector<int>& sources) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    for (int s : sources) { dist[s] = 0; pq.push({0, s}); }   // all sources start at 0
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
    }
    return dist;
}

Tổng quát hơn, mỗi nguồn có thể xuất phát với một khoảng cách ban đầu khác nhau $c_s$ (tương đương cạnh $S^{*}\to s$ trọng số $c_s$). Khi đó chỉ cần dist[s] = min(dist[s], c_s) rồi đẩy vào hàng đợi. $c_s$ được phép âm: chứng minh ở trên chỉ cần trọng số cạnh không âm, còn nhãn ban đầu âm tương đương với nút nguồn ảo nối tới $s$ bằng cạnh $c_s$ rồi tịnh tiến mọi khoảng cách đi một hằng số, không ảnh hưởng thứ tự chốt. Việc cộng một hằng số lớn cho mọi $c_s$ để đưa về không âm (rồi trừ lại ở cuối) chỉ là tùy chọn, ví dụ để khỏi phải nghĩ với số âm hoặc để dùng kiểu không dấu. Nếu cần biết đỉnh $v$ "thuộc về" nguồn nào, lưu thêm $src[v]$ và gán $src[v]=src[u]$ khi nới lỏng.

Đồ thị trạng thái mở rộng

Nhiều bài có ràng buộc làm cho "khoảng cách tới đỉnh $u$" chưa đủ để mô tả trạng thái: còn bao nhiêu vé miễn phí, đang đi theo hướng nào, đã lấy chìa khóa chưa... Khi đó đỉnh mới là cặp $(u,\text{trạng thái phụ})$ và ta chạy Dijkstra trên đồ thị mới này. Số đỉnh nhân lên theo số trạng thái phụ, nên trạng thái phụ phải nhỏ.

Ví dụ: đi từ $s$ tới $t$, được chọn tối đa $K$ cạnh để đi miễn phí. Đỉnh là $(u,j)$ với $j$ là số vé đã dùng:

// Shortest s -> t when at most K edges may be used for free
ll freeEdges(int n, const vector<vector<pair<int, ll>>>& adj, int s, int t, int K) {
    vector<vector<ll>> dist(n + 1, vector<ll>(K + 1, INF));
    // entry = {distance, vertex, coupons used}
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<tuple<ll, int, int>>> pq;
    dist[s][0] = 0;
    pq.push({0, s, 0});
    while (!pq.empty()) {
        auto [d, u, j] = pq.top(); pq.pop();
        if (d != dist[u][j]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v][j]) {               // pay for the edge
                dist[v][j] = d + w;
                pq.push({dist[v][j], v, j});
            }
            if (j < K && d < dist[v][j + 1]) {      // use one coupon: edge costs 0
                dist[v][j + 1] = d;
                pq.push({d, v, j + 1});
            }
        }
    }
    return *min_element(dist[t].begin(), dist[t].end());
}

Độ phức tạp: $O(K(V+E)\log (KV))$, vì đồ thị trạng thái có $K+1$ bản sao của mỗi đỉnh và mỗi cạnh.

Thêm nút trung gian để giảm số cạnh. Đôi khi mô hình đúng lại sinh quá nhiều cạnh. Ví dụ điển hình: một nhóm $k$ đỉnh mà đi giữa hai đỉnh bất kỳ trong nhóm tốn $c$ (một tuyến xe buýt, một "cổng dịch chuyển"). Nối trực tiếp tốn $k^2$ cạnh. Thay vào đó thêm một nút ảo $H$ cho nhóm: cạnh $u\to H$ trọng số $c$ và $H\to v$ trọng số $0$ cho mọi $u,v$ trong nhóm, chỉ còn $2k$ cạnh mà mọi khoảng cách giữa các đỉnh thật không đổi. Lưu ý đây là các cạnh có hướng: chỉ adj[u].push_back, không thêm cả hai chiều như code mẫu cơ bản, vì nếu có thêm cạnh ngược $v\to H$ trọng số $0$ thì đi $v\to H\to w$ chỉ tốn $0$, tức di chuyển trong nhóm thành miễn phí. Mẹo này dùng được bất cứ khi nào chi phí chuyển tiếp tách được thành "phần phụ thuộc chỗ vào" cộng "phần phụ thuộc chỗ ra".

Một mẹo nhỏ đi kèm: "khoảng cách" không nhất thiết là một số. Nếu bài yêu cầu "chi phí nhỏ nhất, hòa thì ít chặng nhất", dùng $dist$ là cặp (chi phí, số chặng) so sánh từ điển; Dijkstra vẫn đúng vì cộng cặp không âm không làm cặp nhỏ đi.

Đếm số đường đi ngắn nhất

Gọi $cnt[v]$ là số đường đi ngắn nhất từ $s$ tới $v$. Khi nới lỏng cạnh $u\to v$ với $nd=dist[u]+w$:

• $nd<dist[v]$: tìm thấy đường ngắn hơn hẳn, mọi đường cũ bị loại: $cnt[v]=cnt[u]$.
• $nd=dist[v]$: thêm một cách đi tới $v$ bằng đúng khoảng cách tối ưu: .

// inside the main loop, after "if (d != dist[u]) continue;"  (cnt[s] = 1 initially)
for (auto [v, w] : adj[u]) {
    ll nd = d + w;
    if (nd < dist[v]) {                     // strictly better: reset the count
        dist[v] = nd;
        cnt[v] = cnt[u];
        pq.push({nd, v});
    } else if (nd == dist[v]) {             // another shortest way into v
        cnt[v] = (cnt[v] + cnt[u]) % MOD;
    }
}

Vì sao đúng: khi $u$ được chốt, mọi đỉnh $p$ có cạnh $p\to u$ nằm trên đường ngắn nhất đều có $dist[p]=dist[u]-w<dist[u]$ (với $w\ge 1$), nên đã được chốt và đã cộng xong vào $cnt[u]$. Do đó $cnt[u]$ lúc chốt là giá trị cuối cùng. Số đường có thể tăng theo hàm mũ, nên thường phải lấy modulo hoặc chặn trên.

Cùng khuôn này có thể tính "đường ngắn nhất, hòa thì ít cạnh nhất / nhiều cạnh nhất" bằng cách thay phép cộng cnt bằng min/max.

DAG đường đi ngắn nhất

Chạy Dijkstra từ $s$ được $d_s$, và từ $t$ trên đồ thị ngược được $d_t$. Khi đó:

• Cạnh $u\to v$ (trọng số $w$) thuộc một đường ngắn nhất nào đó từ $s$ khi $d_s[u]+w=d_s[v]$.
• Cạnh $u\to v$ thuộc một đường ngắn nhất nào đó từ $s$ tới $t$ khi $d_s[u]+w+d_t[v]=d_s[t]$.
• Đỉnh $v$ nằm trên một đường ngắn nhất $s\to t$ khi $d_s[v]+d_t[v]=d_s[t]$.

Với ví dụ ở trên (s = 1, t = 5):
  d_s = [0, 3, 1, 4, 7]      d_t = [7, 4, 6, 3, 0]

  Cạnh 1->3: 0+1+6 = 7  ✓     Cạnh 1->2: 0+4+4 = 8  ✗
  Cạnh 3->2: 1+2+4 = 7  ✓     Cạnh 3->4: 1+5+3 = 9  ✗
  Cạnh 2->4: 3+1+3 = 7  ✓     Cạnh 4->5: 4+3+0 = 7  ✓

  DAG đường ngắn nhất 1 -> 5:   1 -> 3 -> 2 -> 4 -> 5

Các cạnh thỏa điều kiện tạo thành một DAG (với trọng số dương, $d_s$ tăng thật sự dọc mỗi cạnh nên không thể có chu trình). Sắp các đỉnh theo $d_s$ tăng dần là có ngay một thứ tự topo, nên có thể quy hoạch động trên DAG này: đếm đường, tìm đường ngắn nhất thỏa thêm tiêu chí phụ, tìm cạnh mà mọi đường ngắn nhất đều đi qua... Kỹ thuật "tính $d_s$, $d_t$ rồi kiểm tra đẳng thức" cũng là cách chuẩn để trả lời nhanh câu hỏi "cạnh này có nằm trên đường ngắn nhất không".

Bài tập luyện

Luyện kỹ thuật

• Chặn đường (rblock14) (Trung cấp) truy vết một đường ngắn nhất bằng par[], nhận ra chỉ cạnh trên đường đó mới đáng thử nhân đôi, rồi chạy lại Dijkstra cho mỗi cạnh.
• Hai GPS Đối Đầu (gpsduel) (Trung cấp) Dijkstra từ đích trên đồ thị ngược cho từng GPS, dùng đẳng thức $d[u]=w+d[v]$ để nhận diện cạnh thuộc DAG đường ngắn nhất, rồi Dijkstra lần ba với trọng số mới là "số lần phàn nàn".
• Chuyến Bay Giá Rẻ (Silver) (cowroutes) (Trung cấp) khoảng cách là cặp (chi phí, số chặng) so sánh từ điển; đồ thị sinh từ các chuyến bay rất dày nên đáng cân nhắc bản Dijkstra $O(V^2)$.
• Ăn ngon (dining) (Nâng cao) một lần Dijkstra từ chuồng, sau đó Dijkstra đa nguồn trong đó mỗi kiện cỏ là một nguồn với khoảng cách ban đầu phụ thuộc độ ngon (tương đương thêm nút nguồn ảo).
• Bessla Motors (bessla) (Nâng cao) Dijkstra đa nguồn nhưng mỗi đỉnh cần biết tới $K$ nguồn khác nhau, nên trạng thái mở rộng thành (đỉnh, nguồn) và cắt nhánh theo giới hạn $R$; điểm mấu chốt là mỗi đỉnh chỉ giữ tối đa $K$ nguồn đầu tiên tới được nó, nên có $O(KN)$ trạng thái và $O(KM)$ lần nới lỏng.

Đề VOI

• Robot cứu hỏa (voi07_robot) (Nâng cao) VOI 2007: robot bắt buộc đi đường nhanh nhất, nên sau Dijkstra hãy giữ lại DAG đường đi ngắn nhất rồi chặt nhị phân dung lượng pin.
• Hành trình du lịch (voi13_tours) (Nâng cao) VOI 2013: cần chu trình rẻ nhất đi qua mỗi đỉnh. Hãy nghĩ xem nên chạy Dijkstra từ đâu, và cắt tỉa thế nào để đủ nhanh.
• Tàu điện ngầm (voi17_metro) (Nâng cao) VOI 2017: chi phí chuyển tuyến phụ thuộc cả tuyến đến lẫn tuyến đi nên đỉnh của Dijkstra phải là tuyến đường chứ không phải ga; hàm chi phí tách được, nên thêm nút trung gian mỗi ga để tránh bùng nổ số cạnh.
• Cải thiện đánh giá (voi24_impev) (Nâng cao) VOI 2024: bắt đầu bằng hai lần Dijkstra từ thành phố 1 và 2, rồi nhận xét rằng khi cải tạo một con đường thì chỉ hai đầu của nó là cần xét lại.
• Chất lượng dịch vụ (voi14_qos) (Kỳ cựu) VOI 2014: Dijkstra trên đồ thị ngược từ $t$, sau đó "độ dư" so với đường ngắn nhất rất nhỏ ($<100$) nên đếm số đường trên đồ thị trạng thái (nút, độ dư) và dựng đường thứ $k$ theo thứ tự từ điển.
• Tập thể dục (voi19_wout) (Chuyên gia) VOI 2019: nhiều lần Dijkstra (từ điểm đầu và điểm cuối của từng người) để dựng DAG đường ngắn nhất của Nam bằng đẳng thức $d(u)+w+e(v)=D$, rồi quy hoạch động trên DAG theo thứ tự $d$ tăng dần.