Wiki › Thuật toán › Thuật toán đồ thị › k đường đi ngắn nhất

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

Tìm độ dài k đường đi ngắn nhất từ s tới t: Dijkstra cho mỗi đỉnh lấy ra tối đa k lần, A*, thuật toán Eppstein với heap trái bền vững trong O(m log m + k log k), quy hoạch động top-k trên DAG và thuật toán Yen cho đường đi đơn.

huunguyen huunguyen Updated Tháng 11. 17, 2026 Đọc 25 phút 9 lượt xem

Bài toán k đường đi ngắn nhất (k shortest paths) hỏi: trên đồ thị có trọng số không âm, liệt kê độ dài của k đường đi rẻ nhất từ s tới t (không chỉ đường ngắn nhất như Dijkstra). Liệt kê hết mọi đường đi là bất khả thi vì số đường có thể vô hạn (đồ thị có chu trình) hoặc mũ theo n. Trang này trình bày ba cách cho phiên bản cho phép lặp đỉnh (walk): Dijkstra cho mỗi đỉnh được lấy ra tối đa k lần trong O(k·mlog(km)), tăng tốc bằng A*, và thuật toán Eppstein trong O(mlogm+klogk) dùng heap bền vững. Cuối trang là quy hoạch động "danh sách top-k" trên DAG và thuật toán Yen cho phiên bản đường đi đơn (không lặp đỉnh).

Hai phiên bản của bài toán

Đường đi cho phép lặp (walk) Đường đi đơn (simple path)
Được đi qua một đỉnh nhiều lần? Có Không
Hai đường khác nhau khi Dãy cạnh khác nhau Dãy đỉnh (cạnh) khác nhau
Thuật toán k lần Dijkstra, A*, Eppstein Yen
Độ phức tạp điển hình O(mlogm+klogk) O(k·n·mlogn)

Đề thi lập trình hầu hết hỏi phiên bản walk (ví dụ "các chuyến bay có thể đi qua một thành phố nhiều lần"). Đọc kỹ đề: hai đường cùng độ dài thường vẫn được tính là hai đường khác nhau, còn bài "đường đi ngắn nhì" đôi khi chỉ xét các độ dài khác nhau.

Ví dụ xuyên suốt trang: đồ thị có hướng 5 đỉnh, tìm các đường đi từ s=1 tới t=5.

graph directed weighted
5 8
1 2 2
1 3 1
3 2 1
2 4 2
3 4 4
4 5 1
2 5 5
4 2 1
highlight green 1
highlight red 5

Liệt kê bằng tay, sáu đường rẻ nhất là:

Thứ tự Đường đi Độ dài
1 1→2→4→5 2+2+1=5
2 1→3→2→4→5 1+1+2+1=5
3 1→3→4→5 1+4+1=6
4 1→2→5 2+5=7
5 1→3→2→5 1+1+5=7
6 1→2→4→2→4→5 2+2+1+2+1=8

Đường thứ 6 đi vòng 2→4→2 một lần: đó là lý do có vô số đường đi, và vì sao không thể "liệt kê hết rồi sắp xếp".

Cách 1: Dijkstra cho mỗi đỉnh lấy ra tối đa k lần

Ý tưởng

Dijkstra thường lấy mỗi đỉnh ra khỏi hàng đợi một lần, ở lần đó ta có đường ngắn nhất tới nó. Bây giờ ta đưa vào hàng đợi từng đường đi (biểu diễn bởi cặp (độ dài, đỉnh cuối)), không gộp các đường tới cùng một đỉnh. Mỗi lần lấy ra đường (d,u), ta nối thêm mọi cạnh u→v để được các đường (d+w,v).

Vì mọi trọng số không âm, các đường được lấy ra theo thứ tự độ dài không giảm (cùng lý luận với Dijkstra thường). Do đó lần thứ j đỉnh v được lấy ra chính là đường ngắn thứ j từ s tới v, và các lần lấy t ra cho đúng đáp án.

Nếu chỉ có thế thì hàng đợi phình vô hạn. Nhận xét then chốt cho phép cắt tỉa:

Nếu một đường W từ s tới t nằm trong k đường ngắn nhất tới t và đi qua đỉnh u, thì phần đầu P của W (từ s tới u) nằm trong k đường ngắn nhất tới u.

Chứng minh. Giả sử có ít nhất k đường tới u ngắn hơn hẳn P. Ghép mỗi đường đó với phần đuôi của W (từ u tới t) được k đường khác nhau tới t, đều ngắn hơn hẳn W, mâu thuẫn với việc W nằm trong k đường ngắn nhất. (Khi có các đường bằng độ dài, thứ tự giữa chúng là tùy ý nên vẫn chọn được một bộ k đường tốt nhất thỏa tính chất trên.)

Vậy mỗi đỉnh chỉ cần được mở rộng ở k lần lấy ra đầu tiên; các lần sau bỏ qua. Mỗi đỉnh mở rộng tối đa k lần nên tổng số lần đẩy vào hàng đợi không quá k·m.

Ví dụ chạy tay

Chạy với k=3 trên đồ thị ví dụ. cnt[u] là số lần u đã được lấy ra.

Bước Lấy ra (d,u) Đường tương ứng cnt[u] Ghi chú
1 (0,1) 1 1 đẩy (2,2),(1,3)
2 (1,3) 1→3 1 đẩy (2,2),(5,4)
3 (2,2) 1→2 1 đẩy (4,4),(7,5)
4 (2,2) 1→3→2 2 đẩy (4,4),(7,5)
5 (4,4) 1→2→4 1 đẩy (5,5),(5,2)
6 (4,4) 1→3→2→4 2 đẩy (5,5),(5,2)
7 (5,2) 1→2→4→2 3 đẩy (7,4),(10,5); từ giờ cnt[2]=k
8 (5,2) 1→3→2→4→2 bỏ qua vì cnt[2]=k
9 (5,4) 1→3→4 3 đẩy (6,5); cạnh 4→2 không đẩy vì cnt[2]=k
10 (5,5) 1→2→4→5 1 đáp án thứ 1: 5
11 (5,5) 1→3→2→4→5 2 đáp án thứ 2: 5
12 (6,5) 1→3→4→5 3 đáp án thứ 3: 6, dừng

(Các phần tử cùng độ dài có thể ra theo thứ tự khác tùy cài đặt hàng đợi; dãy độ dài in ra thì không đổi.) Code chỉ lưu cặp (độ dài, đỉnh), cột "đường tương ứng" chỉ để minh họa. Chạy chương trình bên dưới với k=6 được 5 5 6 7 7 8, khớp bảng liệt kê tay.

Cài đặt

Input: dòng đầu n,m,k; m dòng u v w là cạnh có hướng u→v trọng số w≥0. In độ dài k đường đi ngắn nhất từ 1 tới n; nếu chỉ có ít hơn k đường thì in −1 cho các vị trí còn thiếu.

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

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<pair<int, ll>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        scanf("%d %d %lld", &u, &v, &w);
        adj[u].push_back({v, w});
    }
    int s = 1, t = n;
    vector<int> cnt(n + 1, 0);          // how many times each vertex was popped
    vector<ll> ans;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    pq.push({0, s});
    while (!pq.empty() && (int)ans.size() < k) {
        auto [d, u] = pq.top(); pq.pop();
        if (cnt[u] == k) continue;      // u already has its k best walks
        cnt[u]++;
        if (u == t) ans.push_back(d);   // record on POP, not on push
        for (auto [v, w] : adj[u])
            if (cnt[v] < k) pq.push({d + w, v});
    }
    while ((int)ans.size() < k) ans.push_back(-1);   // fewer than k walks exist
    for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}
Python
import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, w = int(data[3 + 3*i]), int(data[4 + 3*i]), int(data[5 + 3*i])
        adj[u].append((v, w))
    s, t = 1, n
    cnt = [0] * (n + 1)          # how many times each vertex was popped
    ans = []
    pq = [(0, s)]
    while pq and len(ans) < k:
        d, u = heapq.heappop(pq)
        if cnt[u] == k:
            continue             # u already has its k best walks
        cnt[u] += 1
        if u == t:
            ans.append(d)        # record on pop, not on push
        for v, w in adj[u]:
            if cnt[v] < k:
                heapq.heappush(pq, (d + w, v))
    ans += [-1] * (k - len(ans))
    print(*ans)

main()

Với input ví dụ (5 8 6 rồi tám cạnh như hình), cả hai chương trình in 5 5 6 7 7 8.

Độ phức tạp
  • Thời gian O(k·mlog(km)): mỗi đỉnh được mở rộng tối đa k lần, mỗi lần duyệt hết cạnh ra của nó, nên tổng số lần đẩy vào hàng đợi ≤k·m (cộng 1 lần đẩy s). Mỗi thao tác hàng đợi tốn O(log(km)).
  • Bộ nhớ O(n+km): hàng đợi có thể chứa tới km phần tử.

Cách này rất ngắn và là lựa chọn mặc định khi k nhỏ (cỡ k≤10 đến 100). Khi k lên tới 105 thì k·m quá lớn, cần Eppstein.

Tăng tốc bằng A* với hàm ước lượng chính xác

Tính trước h(v) = khoảng cách ngắn nhất từ v tới t (chạy Dijkstra từ t trên đồ thị ngược). Trong hàng đợi, xếp đường (d,v) theo khóa d+h(v) thay vì d. Đây là thuật toán A* với hàm ước lượng chính xác:

  • Với cùng một đỉnh v, h(v) là hằng số nên các lần lấy v ra vẫn theo thứ tự d tăng dần, nhận xét "chỉ mở rộng k lần đầu" vẫn đúng. Với t thì h(t)=0, khóa chính là độ dài.
  • Đỉnh có h(v)=∞ (không tới được t) không bao giờ được đẩy vào. Điều này loại bỏ hẳn những vùng đồ thị vô ích, và nếu không có đường nào tới t thì hàng đợi rỗng ngay.
  • Đường đi "lệch" khỏi đường ngắn nhất càng ít thì khóa càng nhỏ, nên thuật toán đi thẳng về phía t thay vì loang đều mọi hướng.

Chặn trên lý thuyết vẫn là O(k·mlog(km)), nhưng trên thực tế nhanh hơn nhiều. Ý tưởng "độ dài thật = khoảng cách ngắn nhất + phần lệch" chính là nền của thuật toán Eppstein.

Cách 2: thuật toán Eppstein

Cây đường đi ngắn nhất và cạnh rẽ nhánh

Chạy Dijkstra từ t trên đồ thị ngược, được dist[v] = khoảng cách ngắn nhất từ v tới t. Mỗi đỉnh v≠t tới được t chọn đúng một cạnh v→p(v) thỏa dist[v]=w+dist[p(v)]: các cạnh này tạo thành cây đường đi ngắn nhất T gốc t. Đi từ v theo cây là đi đường ngắn nhất tới t.

Mọi cạnh e=(u→v,w) còn lại (với dist[v]<∞) gọi là cạnh rẽ nhánh (sidetrack), gắn với độ lệch

δ(e)=w+dist[v]−dist[u] ≥0.

δ(e) là chi phí phải trả thêm khi tại u, thay vì đi theo cây, ta rẽ sang e rồi đi tiếp đường ngắn nhất từ v. Với cạnh của cây thì độ lệch bằng 0.

Mỗi đường đi là một dãy cạnh rẽ nhánh

Xét một đường W từ s tới t. Bỏ các cạnh của cây, giữ lại các cạnh rẽ nhánh theo thứ tự xuất hiện: e1,e2,…,er. Giữa hai cạnh rẽ nhánh liên tiếp, W đi theo cây. Cộng các độ lệch dọc W, các số hạng dist triệt tiêu dạng tổng lồng nhau:

len(W)=dist[s]+∑i=1rδ(ei).

Ngược lại, một dãy cạnh rẽ nhánh e1,…,er xác định đúng một đường đi khi và chỉ khi: e1 xuất phát từ một đỉnh trên đường cây s⤳t, và với mỗi i, ei+1 xuất phát từ một đỉnh trên đường cây từ đầu cuối của ei tới t. Vậy:

Bài toán trở thành: liệt kê k dãy cạnh rẽ nhánh hợp lệ có tổng độ lệch nhỏ nhất. Dãy rỗng là đường ngắn nhất, độ dài dist[s].

Heap gom cạnh rẽ nhánh dọc đường cây

Gọi H(v) là heap nhỏ nhất chứa mọi cạnh rẽ nhánh xuất phát từ các đỉnh trên đường cây v⤳t, khóa là δ. Từ định nghĩa:

H(v)={cạnh rẽ nhánh đi ra từ v}∪H(p(v)),H(t)={cạnh rẽ nhánh đi ra từ t}.

Nếu sao chép H(p(v)) cho từng v thì tốn O(nm). Dùng heap trái bền vững (persistent leftist heap): phép gộp chỉ đi dọc đường bên phải (dài O(log)) và sao chép các nút trên đường đó thay vì sửa, nên phiên bản cũ H(p(v)) vẫn nguyên vẹn và H(v) dùng chung phần lớn nút với nó. Đây cùng tư tưởng với segment tree bền vững; xem heap để ôn tính chất heap. Xử lý các đỉnh theo thứ tự dist tăng dần (thứ tự Dijkstra lấy ra) thì p(v) luôn xong trước v.

Duyệt các dãy theo thứ tự tổng độ lệch

Mỗi trạng thái là một nút x của một heap H(·), biểu diễn một dãy mà cạnh rẽ nhánh cuối cùng là cạnh tại nút x; giá trị trạng thái là độ dài đường đi tương ứng c. Từ trạng thái (c,x) có tối đa ba bước đi tiếp:

  1. Thay cạnh cuối bằng con trái xL của x trong heap: c−δ(x)+δ(xL).
  2. Thay cạnh cuối bằng con phải xR: c−δ(x)+δ(xR).
  3. Giữ cạnh cuối, nối thêm cạnh rẽ nhánh nhỏ nhất sau nó: với v là đầu cuối của cạnh tại x, đi tới gốc của H(v) với giá trị c+δ(gốc H(v)).

Trạng thái đầu là gốc của H(s) với giá trị dist[s]+δ(gốc). Vì sao đúng:

  • Không giảm: heap có tính chất con ≥ cha nên bước 1, 2 không làm giảm c; bước 3 cộng thêm δ≥0. Mọi bước đều không giảm.
  • Đầy đủ và không trùng: mỗi dãy hợp lệ đi tới được từ trạng thái đầu bằng đúng một chuỗi bước: với mỗi cạnh ei, nó nằm ở đúng một nút trong heap tương ứng và đường từ gốc tới nút đó trong cây heap là duy nhất. Vậy các trạng thái tạo thành một cây có cạnh không âm.

Duyệt cây này bằng hàng đợi ưu tiên (giống Dijkstra trên cây) sẽ lấy ra các trạng thái theo thứ tự giá trị không giảm, mỗi trạng thái đúng một lần. Mỗi lần lấy ra đẩy vào tối đa 3 trạng thái, nên lấy k lần chỉ tốn O(klogk).

Ví dụ chạy tay

Trên đồ thị ví dụ, t=5. Dijkstra trên đồ thị ngược:

Đỉnh v 5 4 2 3 1
dist[v] 0 1 3 4 5
Cạnh cây v→p(v) 4→5 2→4 3→2 1→2

Đỉnh 1 có hai lựa chọn cùng tốt (1→2 và 1→3, đều cho 5); cài đặt chọn cạnh tìm thấy trước là 1→2. Cây đường đi ngắn nhất (màu xanh) và bốn cạnh rẽ nhánh (màu cam):

graph directed weighted
5 8
1 2 2
1 3 1
3 2 1
2 4 2
3 4 4
4 5 1
2 5 5
4 2 1
highlight green 1-2 3-2 2-4 4-5
highlight orange 1-3 3-4 2-5 4-2
label 1 d=5
label 2 d=3
label 3 d=4
label 4 d=1
label 5 d=0

Độ lệch các cạnh rẽ nhánh δ=w+dist[v]−dist[u]:

Cạnh rẽ nhánh 1→3 3→4 2→5 4→2
δ 1+4−5=0 4+1−4=1 5+0−3=2 1+3−1=3

Các heap (ghi theo khóa): H(5)=∅, H(4)={3}, H(2)={2}∪H(4)={2,3}, H(3)={1}∪H(2)={1,2,3}, H(1)={0}∪H(2)={0,2,3}. Lưu ý H(1) và H(3) dùng chung các nút của H(2), không sao chép.

Các đường đi lấy ra theo thứ tự:

Thứ tự Dãy cạnh rẽ nhánh Độ dài =5+∑δ Đường đi
1 (rỗng) 5 1→2→4→5
2 1→3 5+0=5 1→3→2→4→5
3 1→3, 3→4 5+0+1=6 1→3→4→5
4 2→5 5+2=7 1→2→5
5 1→3, 2→5 5+0+2=7 1→3→2→5
6 4→2 5+3=8 1→2→4→2→4→5

Ở dòng 3: sau cạnh 1→3 ta ở đỉnh 3, bước "nối thêm" lấy gốc của H(3) là cạnh 3→4 với δ=1. Dòng 6 còn hòa với dãy 1→3, 4→2 (cũng độ dài 8), là đường thứ 7. Kết quả khớp đúng bảng liệt kê tay ở đầu trang.

Cài đặt

Cùng định dạng input/output như cách 1. Heap trái lưu trong một vector toàn cục, nút 0 là heap rỗng.

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

// Persistent leftist heap: merge copies nodes, old versions stay valid.
struct Node { ll key; int to; int l, r, rk; };
vector<Node> T = {{0, 0, 0, 0, 0}};     // node 0 = empty heap (rk = 0)

int newNode(ll key, int to) { T.push_back({key, to, 0, 0, 1}); return (int)T.size() - 1; }

int merge(int a, int b) {
    if (!a || !b) return a | b;
    if (T[a].key > T[b].key) swap(a, b);
    int c = (int)T.size(); T.push_back(T[a]);       // copy root of a
    int nr = merge(T[c].r, b);                     // T may reallocate: use index
    T[c].r = nr;
    if (T[T[c].l].rk < T[T[c].r].rk) swap(T[c].l, T[c].r);
    T[c].rk = T[T[c].r].rk + 1;
    return c;
}

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<int> eu(m), ev(m); vector<ll> ew(m);
    vector<vector<int>> radj(n + 1);           // incoming edges, for Dijkstra from t
    for (int i = 0; i < m; i++) {
        scanf("%d %d %lld", &eu[i], &ev[i], &ew[i]);
        radj[ev[i]].push_back(i);
    }
    int s = 1, t = n;

    // 1) Dijkstra on the reversed graph: dist[v] = shortest v -> t.
    vector<ll> dist(n + 1, INF);
    vector<int> treeEdge(n + 1, -1), order;    // treeEdge[v]: the ONE edge v -> next on the tree
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[t] = 0; pq.push({0, t});
    vector<bool> done(n + 1, false);
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (done[v]) continue;
        done[v] = true; order.push_back(v);    // order = increasing dist
        for (int e : radj[v]) {
            int u = eu[e];
            if (d + ew[e] < dist[u]) { dist[u] = d + ew[e]; treeEdge[u] = e; pq.push({dist[u], u}); }
        }
    }

    vector<ll> ans;
    if (dist[s] < INF) {
        // 2) h[v] = heap of all sidetrack edges on the tree path v -> t.
        vector<vector<int>> out(n + 1);
        for (int i = 0; i < m; i++) out[eu[i]].push_back(i);
        vector<int> h(n + 1, 0);
        for (int v : order) {                  // parent is processed before child
            int base = (v == t) ? 0 : h[ev[treeEdge[v]]];
            for (int e : out[v]) {
                if (e == treeEdge[v] || dist[ev[e]] >= INF) continue;
                ll delta = ew[e] + dist[ev[e]] - dist[v];   // extra cost, always >= 0
                base = merge(base, newNode(delta, ev[e]));
            }
            h[v] = base;
        }
        // 3) Best-first search over "sidetrack sequences".
        ans.push_back(dist[s]);                // the shortest walk itself
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
        if (h[s]) q.push({dist[s] + T[h[s]].key, h[s]});
        while (!q.empty() && (int)ans.size() < k) {
            auto [c, x] = q.top(); q.pop();
            ans.push_back(c);
            // replace the last sidetrack by a sibling candidate in the same heap
            if (T[x].l) q.push({c - T[x].key + T[T[x].l].key, T[x].l});
            if (T[x].r) q.push({c - T[x].key + T[T[x].r].key, T[x].r});
            // keep the last sidetrack and append a new one after its head
            int y = h[T[x].to];
            if (y) q.push({c + T[y].key, y});
        }
    }
    while ((int)ans.size() < k) ans.push_back(-1);
    for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}

Với input ví dụ, chương trình in 5 5 6 7 7 8. Trên đồ thị ngẫu nhiên n=105, m=2·105, k=2·105, chương trình chạy khoảng 0.2 giây.

Độ phức tạp
  • Dijkstra ngược: O(mlogm).
  • Dựng heap: mỗi cạnh rẽ nhánh được chèn bằng một phép merge; phép gộp heap trái đi dọc đường bên phải, dài O(logm), và tạo O(logm) nút mới. Tổng O(mlogm) thời gian và bộ nhớ.
  • Liệt kê: k lần lấy ra, mỗi lần đẩy tối đa 3 trạng thái, hàng đợi có O(k) phần tử: O(klogk).
  • Tổng: thời gian O(mlogm+klogk), bộ nhớ O(mlogm+k).

(Bài báo gốc của Eppstein đạt O(m+nlogn+k) bằng các cấu trúc tinh vi hơn; phiên bản heap trái ở trên là bản dùng trong thi đấu.)

Trên DAG: quy hoạch động danh sách top-k

Khi đồ thị không có chu trình, có cách đơn giản hơn: với mỗi đỉnh v, lưu L[v] là danh sách (đã sắp xếp) tối đa k độ dài nhỏ nhất của các đường từ s tới v. Duyệt theo thứ tự tô pô:

L[v]=k nhỏ nhất của ⋃(u→v, w){x+w:x∈L[u]},L[s]∋0.

Đúng vì cùng nhận xét "phần đầu của một đường tốt cũng là đường tốt": một đường trong top-k tới v có cạnh cuối u→v thì phần trước nó nằm trong top-k tới u. DAG đảm bảo khi xử lý v thì mọi L[u] đã xong. Cách này cho phép cạnh âm (Dijkstra thì không) và cũng dùng cho "k đường dài nhất" trên DAG.

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

int main() {
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<vector<pair<int, ll>>> radj(n + 1);   // incoming edges
    vector<vector<int>> adj(n + 1);
    vector<int> indeg(n + 1, 0);
    for (int i = 0; i < m; i++) {
        int u, v; ll w;
        scanf("%d %d %lld", &u, &v, &w);
        radj[v].push_back({u, w}); adj[u].push_back(v); indeg[v]++;
    }
    // Kahn's topological order
    vector<int> order, q;
    for (int v = 1; v <= n; v++) if (!indeg[v]) q.push_back(v);
    for (size_t i = 0; i < q.size(); i++) {
        int u = q[i]; order.push_back(u);
        for (int v : adj[u]) if (--indeg[v] == 0) q.push_back(v);
    }
    // L[v] = sorted list of the (at most) k smallest path lengths 1 -> v
    vector<vector<ll>> L(n + 1);
    for (int v : order) {
        vector<ll> cand;
        if (v == 1) cand.push_back(0);           // the empty path
        for (auto [u, w] : radj[v])
            for (ll x : L[u]) cand.push_back(x + w);
        if ((int)cand.size() > k) {
            nth_element(cand.begin(), cand.begin() + k, cand.end());
            cand.resize(k);                      // keep only the k smallest
        }
        sort(cand.begin(), cand.end());
        L[v] = cand;
    }
    vector<ll> ans = L[n];
    while ((int)ans.size() < k) ans.push_back(-1);
    for (int i = 0; i < k; i++) printf("%lld%c", ans[i], i + 1 < k ? ' ' : '\n');
}

Độ phức tạp: đỉnh v gom deg−(v)·k ứng viên, nth_element chạy tuyến tính, rồi sắp xếp k phần tử: tổng O(mk+nklogk) thời gian, O(nk) bộ nhớ. Nếu chỉ cần đếm hoặc tìm đường thứ k theo thứ tự từ điển, ta thay danh sách bằng số đếm (chặn trên ở k) rồi dựng đường từng bước.

Đường đi đơn: thuật toán Yen

Khi đề cấm lặp đỉnh, các cách trên sai (chúng sẽ đếm cả đường đi vòng như đường thứ 6 ở ví dụ). Thuật toán Yen tìm k đường đơn ngắn nhất:

  1. A1 = đường ngắn nhất (Dijkstra).
  2. Để tìm Ai: với mỗi đỉnh rẽ r trên Ai−1 (trừ t), gọi gốc là đoạn Ai−1 từ s tới r.
    • Xóa tạm mọi cạnh r→x mà một đường Aj đã tìm (j<i) có cùng gốc rồi đi tiếp bằng cạnh đó.
    • Xóa tạm các đỉnh trong gốc (trừ r) để đường mới không lặp đỉnh.
    • Dijkstra từ r tới t trên đồ thị còn lại; nếu có, ghép gốc với đoạn này thành một ứng viên, đưa vào tập ứng viên B (bỏ trùng).
  3. Ai = ứng viên ngắn nhất trong B, xóa nó khỏi B.

Mỗi lần tìm Ai chạy tối đa n lần Dijkstra, nên tổng O(k·n·(m+n)logn). Chỉ dùng được với n, k nhỏ; trong thi đấu phiên bản đường đơn ít gặp hơn hẳn phiên bản walk.

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

  • Ghi nhận đáp án lúc đẩy vào hàng đợi. Triệu chứng: in ra dãy không tăng dần hoặc sai giá trị. Thứ tự chỉ đúng khi lấy ra; ghi nhận t khi pop như code mẫu.
  • Dùng mảng dist và điều kiện if (d > dist[u]) continue như Dijkstra thường. Điều đó gộp mọi đường tới u làm một, chỉ còn đường ngắn nhất. Phải đếm cnt[u] và cho phép lấy ra tới k lần.
  • Quên giới hạn k lần cho các đỉnh khác t. Hàng đợi phình theo cấp số nhân; nếu không có đủ k đường tới t (hoặc t không tới được) thì vòng lặp không dừng trên đồ thị có chu trình. Kiểm tra cnt[u] == k cho mọi đỉnh.
  • Gộp các đường cùng độ dài. Ở ví dụ, hai đường độ dài 5 là hai đáp án khác nhau. Ngược lại, bài "đường ngắn nhì" kiểu d2>d1 hẳn thì phải bỏ qua đường trùng độ dài: đọc kỹ đề định nghĩa "khác nhau" là gì.
  • Eppstein: loại mọi cạnh có δ=0 thay vì đúng một cạnh cây. Triệu chứng: thiếu đường (ở ví dụ, 1→3 có δ=0 nhưng không phải cạnh cây; bỏ nó thì mất đường thứ 2). Lưu chỉ số cạnh cây treeEdge[v] và chỉ bỏ đúng cạnh đó; cạnh song song cùng trọng số vẫn là cạnh rẽ nhánh.
  • Eppstein: thêm cạnh đi tới đỉnh không tới được t. dist[v]=∞ làm δ tràn số. Bỏ qua các cạnh đó, và nếu dist[s]=∞ thì không có đường nào.
  • Eppstein: giữ tham chiếu T[c] qua lời gọi đệ quy merge. push_back có thể cấp phát lại vector, tham chiếu cũ trỏ vào vùng nhớ đã giải phóng. Code mẫu lưu kết quả đệ quy vào biến nr rồi mới gán T[c].r = nr.
  • Tràn số. Độ dài đường thứ k có thể vượt 231 (ví dụ w≤109 và đường đi vòng nhiều lần): dùng long long.
  • Cạnh âm. Cả k lần Dijkstra lẫn Eppstein cần w≥0 (Eppstein cần δ≥0). Với cạnh âm trên DAG dùng quy hoạch động top-k; trên đồ thị tổng quát có chu trình âm thì bài toán không xác định.
  • s=t. Đường rỗng độ dài 0 được tính là một đường (cả hai code đều đếm nó). Nếu đề không tính đường rỗng, bỏ đáp án đầu tiên.

Bài tập luyện

  • Các Tuyến Bay (flightroutes) (Trung bình): k≤10 đường đi rẻ nhất từ 1 tới n, cho phép lặp đỉnh; áp dụng trực tiếp cách lấy mỗi đỉnh ra tối đa k lần.
  • Đường đi ngắn nhì (thhv14_shortest) (Khó): đường ngắn nhì có độ dài lớn hơn hẳn độ dài ngắn nhất, nên phải lưu hai độ dài khác nhau d1<d2 cho mỗi đỉnh thay vì đếm số lần lấy ra.
  • K hành trình ngắn nhất (gr07_kth) (Khó): k hành trình rẻ nhất có khuyên, cạnh song song và trường hợp không đủ k hành trình (in −1); kiểm tra kỹ các bẫy dừng vòng lặp và n=1.
  • Chất lượng dịch vụ (voi14_qos) (Rất khó): tìm đường thứ k theo thứ tự từ điển trong các đường có độ trễ không vượt Tmin+Cmin; dùng dist tới t để tính "độ dư", rồi đếm đường trên DAG trạng thái (đỉnh, độ dư) như mục quy hoạch động trên DAG.

Hiện kho bài CTOJ chưa có bài bắt buộc thuật toán Eppstein (với k cỡ 105); có thể tự kiểm tra cài đặt Eppstein bằng cách nộp lên các bài trên.

Trang này có hữu ích không? Đăng nhập để trả lời

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0