Bỏ qua

Đường đi ngắn nhất thứ k

Kiến thức nền tảng: Thuật toán Dijkstra, Thuật toán A*, Heap hợp nhất có thể truy hồi (Persistent Heap)

Mô tả bài toán

Cho một đồ thị có hướng gồm \(n\) đỉnh, \(m\) cạnh, hãy tìm độ dài của đường đi khác nhau thứ \(k\) ngắn nhất từ \(s\) đến \(t\).

“Đường đi”

Trong tài liệu này, “đường đi” cho phép đi qua cùng một cạnh hoặc cùng một đỉnh nhiều lần, do đó tên gọi chính xác phải là “walk” thay vì “path”. Vấn đề được bàn luận thực chất là bài toán \(k\) đường đi ngắn nhất (\(k\) shortest walk). Tuy nhiên, theo thói quen, tài liệu vẫn dùng từ “đường đi”, còn với đường đi không tự cắt (không đi qua đỉnh/cạnh nào hai lần) thì gọi là “đường đi đơn giản”.

Thuật toán A*

Thuật toán A* là một thuật toán tìm kiếm. Với mỗi trạng thái hiện tại \(x\), thuật toán đặt một hàm đánh giá \(f(x)=g(x)+h(x)\), trong đó \(g(x)\) là chi phí thực tế từ trạng thái khởi đầu đến \(x\), còn \(h(x)\) là ước lượng chi phí tốt nhất từ \(x\) đến trạng thái đích. Khi tìm kiếm, mỗi lần lấy ra trạng thái \(x\) có \(f(x)\) nhỏ nhất để mở rộng các trạng thái kế tiếp. Có thể dùng hàng đợi ưu tiên để duy trì giá trị này.

Khi giải bài toán \(k\) đường đi ngắn nhất, đặt \(h(x)\) là độ dài đường đi ngắn nhất từ đỉnh hiện tại đến đích \(t\). Có thể tiền xử lý giá trị này cho từng đỉnh bằng cách chạy thuật toán đường đi ngắn nhất trên đồ thị ngược từ \(t\). Mỗi trạng thái cần lưu hai giá trị: đỉnh hiện tại \(x\) và tổng quãng đường đã đi \(g(x)\), ký hiệu trạng thái là \((x, g(x))\). Ban đầu, đưa trạng thái \((s, 0)\) vào hàng đợi ưu tiên. Mỗi lần lấy ra trạng thái có \(f(x)=g(x)+h(x)\) nhỏ nhất, liệt kê tất cả các cạnh xuất phát từ \(x\) để sinh trạng thái kế tiếp và đưa vào hàng đợi. Khi một đỉnh được truy cập lần thứ \(k\), thì \(g(x)\) tương ứng chính là độ dài đường đi ngắn thứ \(k\) từ \(s\) đến \(x\).

Quá trình tìm kiếm này có thể tối ưu hơn. Vì chỉ cần tìm \(k\) đường đi ngắn nhất từ \(s\) đến \(t\), nên nếu một đỉnh đã được lấy ra hơn \(k\) lần thì không cần mở rộng trạng thái đó nữa. Trạng thái này sẽ không ảnh hưởng đến đáp án cuối cùng. Lý do là \(k\) lần lấy ra trước đó đã tạo đủ \(k\) đường đi hợp lệ đến đỉnh đó, đủ để xây dựng \(k\) đường đi ngắn nhất đến \(t\).

Nếu dùng hàng đợi ưu tiên để tối ưu Dijkstra, mỗi cạnh tối đa được đưa vào hàng đợi \(k\) lần, nên độ phức tạp thuật toán là \(O(km\log km)\), độ phức tạp bộ nhớ là \(O(km)\). So với tìm kiếm trực tiếp, A* cắt nhánh tốt hơn cho đỉnh đích \(t\), nhưng chỉ cải thiện hằng số chứ không giảm bậc độ phức tạp. Thuật toán này tuy không tối ưu về độ phức tạp, nhưng có thể tìm được \(k\) đường đi ngắn nhất từ \(s\) đến mọi đỉnh (trong cây đường đi ngắn nhất gốc \(t\)) với cùng độ phức tạp.

Cài đặt mẫu

Bài mẫu Library Checker - K-Shortest Walk - Tham khảo cài đặt 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Submission: https://judge.yosupo.jp/submission/311622
#include <iostream>
#include <queue>
#include <vector>

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

struct Edge {
  int u, v, c;

  Edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

int n, m, s, t, k;
std::vector<std::vector<int>> gr, ig;  // Graph and inverse graph.
std::vector<Edge> edges;               // Edges.
std::priority_queue<std::pair<long long, int>,
                    std::vector<std::pair<long long, int>>, std::greater<>>
    pq;

std::vector<long long> dist_t;

// Calculate distances to the destination node t. (Dijkstra)
void calc_distances_to_t() {
  dist_t.assign(n, inf);
  dist_t[t] = 0;
  pq.emplace(dist_t[t], t);
  while (!pq.empty()) {
    long long di = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    if (di > dist_t[cur]) continue;
    for (auto e : ig[cur]) {
      int nxt = edges[e].u;
      auto di_nxt = di + edges[e].c;
      if (di_nxt < dist_t[nxt]) {
        dist_t[nxt] = di_nxt;
        pq.emplace(di_nxt, nxt);
      }
    }
  }
}

std::vector<long long> ans;

// Find the k shortest walk. (A* search)
// Complexity: O(k * n * log(k * n)).
void find_k_shortest_walks() {
  ans.assign(k, -1);
  std::vector<int> cnt(n);
  pq.emplace(dist_t[s], s);
  while (!pq.empty()) {
    long long cost = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    // Skip unreachable nodes.
    if (cost >= inf) continue;
    if (cur == t) ans[cnt[t]] = cost;
    ++cnt[cur];
    // Terminate when the destination has been visited k times.
    if (cnt[t] >= k) break;
    // Expand the same node at most k times.
    if (cnt[cur] > k) continue;
    for (auto e : gr[cur]) {
      int nxt = edges[e].v;
      auto cost_nxt = cost - dist_t[cur] + edges[e].c + dist_t[nxt];
      pq.emplace(cost_nxt, nxt);
    }
  }
}

int main() {
  // Input.
  std::cin >> n >> m >> s >> t >> k;
  gr.resize(n);
  ig.resize(n);
  edges.reserve(m);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    std::cin >> u >> v >> c;
    edges.emplace_back(u, v, c);
    gr[u].push_back(i);
    ig[v].push_back(i);
  }
  // Calculate.
  calc_distances_to_t();
  find_k_shortest_walks();
  // Output.
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

Phương pháp Heap hợp nhất có thể truy hồi (Persistent Heap)

Thuật toán trên thực chất tìm được \(k\) đường đi ngắn nhất đến mọi đỉnh. Nếu chỉ cần tìm \(k\) đường đi ngắn nhất đến một đỉnh đích \(t\) cho trước, ta có thể làm nhanh hơn. Phần này trình bày một phương pháp dựa trên heap hợp nhất có thể truy hồi với độ phức tạp \(O(m\log m + k\log k)\).

Cây đường đi ngắn nhất và cạnh lệch (sidetrack)

Điểm nghẽn của thuật toán trước là chỉ khi đến đích \(t\) mới cập nhật đáp án. Nhưng thực tế, các đường đi khác nhau có thể chỉ khác nhau ở một vài cạnh. Ví dụ, đường đi ngắn thứ hai có thể chỉ khác đường đi ngắn nhất ở một cạnh, còn các đoạn khác giống nhau; nhưng thuật toán trước có thể phải tìm lại toàn bộ các cạnh giống nhau này để tìm đường đi ngắn thứ hai. Vì chỉ đoạn “rẽ nhánh” mới là then chốt, nên để tìm \(k\) đường đi ngắn nhất, chỉ cần xét \(k\) cách rẽ nhánh có chi phí nhỏ nhất. Điều này dẫn đến khái niệm cây đường đi ngắn nhất.

Chạy thuật toán đường đi ngắn nhất trên đồ thị ngược từ \(t\), lưu độ dài đường đi ngắn nhất từ mỗi đỉnh \(x\) đến \(t\) là \(h(x)\), và lưu cạnh đầu tiên trên đường đi ngắn nhất từ \(x\) là \(f_x\) (nếu có nhiều cạnh tối ưu, chọn một bất kỳ). Tập các cạnh \(f_x\) và các đỉnh đầu cuối của chúng tạo thành một cây, trong đó đường đi đơn giản từ mỗi đỉnh \(x\) đến gốc \(t\) là một đường đi ngắn nhất. Đó chính là cây đường đi ngắn nhất \(T\).

Sau khi có cây \(T\), ta có thể tính được mỗi cạnh không thuộc \(T\) sẽ làm đường đi dài hơn bao nhiêu. Với cạnh \(e=(u,v)\notin T\), trọng số \(w\), định nghĩa một cạnh mới cũng từ \(u\) đến \(v\) với chi phí \(\Delta(e)=w + h(v) - h(u)\). Gọi các cạnh này là cạnh lệch (sidetrack), và \(\Delta(e)\) là chi phí lệch. Nếu một cạnh có đỉnh đầu/cuối không nằm trong \(T\), nó không ảnh hưởng đến \(k\) đường đi ngắn nhất đến \(t\), có thể bỏ qua.

Hình dưới: bên trái là đồ thị \(G\), bên phải là cây đường đi ngắn nhất \(T\) (cạnh đậm) và các cạnh lệch (cạnh mảnh):

Gọi tập các cạnh trên đường đi từ \(s\) đến \(t\) là \(P\), loại bỏ các cạnh thuộc \(T\) khỏi \(P\) được \(P'\). Sắp xếp các cạnh trong \(P'\) theo thứ tự xuất hiện, hai cạnh liên tiếp \(e_1=(u_1,v_1)\) và \(e_2=(u_2,v_2)\) phải thỏa mãn:

  • Điều kiện \((*)\): Đỉnh bắt đầu \(u_2\) của cạnh sau là tổ tiên (hoặc chính nó) của đỉnh kết thúc \(v_1\) của cạnh trước trên cây \(T\).

Lý do: trong đường đi gốc \(P\), giữa \(v_1\) và \(u_2\) là một chuỗi các cạnh thuộc \(T\). Ngược lại, với một tập cạnh lệch \(P'\) thỏa mãn \((*)\), tồn tại duy nhất một đường đi \(P\) trong \(G\) tương ứng. Vì đường đi đơn giản trên cây \(T\) là duy nhất. Như vậy, mỗi đường đi \(P\) trong \(G\) tương ứng một chuỗi cạnh lệch \(P'\) thỏa mãn \((*)\). Độ dài đường đi \(P\) là:

\[ h(s)+\sum_{e\in P'}\Delta(e). \]

Vậy, bài toán tìm \(k\) đường đi ngắn nhất chuyển thành tìm \(k\) chuỗi cạnh lệch \(P'\) thỏa mãn \((*)\) có tổng chi phí nhỏ nhất.

Để xử lý điều kiện \((*)\), thay vì mỗi lần truy vấn tổ tiên trên cây \(T\), ta truyền tập cạnh lệch của mỗi đỉnh xuống các con trên cây \(T\). Điều này tương đương xây dựng một đồ thị \(G'\) như sau:

Trên đồ thị này, điều kiện \((*)\) trở thành: các cạnh trong \(P'\) phải nối tiếp nhau, tức \(P'\) là một đường đi trong \(G'\). Bài toán chuyển thành tìm \(k\) đường đi ngắn nhất xuất phát từ \(s\) đến bất kỳ đỉnh nào trong \(G'\).

Bài toán này dễ giải: xuất phát từ \(s\), chạy thuật toán đường đi ngắn nhất. Mỗi lần lấy ra một đỉnh từ hàng đợi ưu tiên là tìm được một đường đi trong \(G'\), tương ứng với một đường đi từ \(s\) đến \(t\) trong \(G\).

Tối ưu bằng Heap hợp nhất có thể truy hồi

Ý tưởng đã rõ, nhưng nếu cài đặt trực tiếp thì độ phức tạp vẫn cao. Vì tại một đỉnh của \(G'\), số cạnh có thể lên tới \(\Theta(m)\), nên mỗi lần mở rộng có thể phải đưa \(\Theta(m)\) cạnh vào hàng đợi. Tuy nhiên, thực tế chỉ cần quan tâm đến những cạnh ngắn nhất. Do đó, có thể gom toàn bộ tập cạnh lệch tại một đỉnh thành một cấu trúc dữ liệu (heap nhỏ nhất), mỗi lần chỉ cần truy cập cạnh nhỏ nhất.

Vậy, dùng heap nhỏ nhất để lưu tập cạnh lệch tại mỗi đỉnh. Trong hàng đợi ưu tiên, chỉ cần lưu các heap này, chi phí là giá trị nhỏ nhất trên đỉnh heap. Mỗi lần lấy heap đầu hàng đợi, lấy ra cạnh nhỏ nhất, rồi đưa heap còn lại (sau khi loại bỏ cạnh này) và heap tại đỉnh đích của cạnh này vào hàng đợi.

Vì cần truyền tập cạnh lệch xuống các con trên cây \(T\), heap cần hỗ trợ hợp nhất (merge) và truy hồi (persistent). Đó chính là heap hợp nhất có thể truy hồi.

Tóm tắt thuật toán:

  1. Từ đích \(t\), chạy thuật toán đường đi ngắn nhất để xây dựng cây đường đi ngắn nhất.
  2. Với mỗi đỉnh trên cây, xây dựng tập cạnh lệch và lưu vào heap hợp nhất có thể truy hồi.
  3. Truyền heap từ mỗi đỉnh xuống các con trên cây \(T\).
  4. Từ \(s\), đưa heap tại \(s\) vào hàng đợi ưu tiên.
  5. Mỗi lần lấy heap đầu hàng đợi, ghi nhận đáp án, rồi đưa heap còn lại (sau khi loại bỏ cạnh nhỏ nhất) và heap tại đỉnh đích của cạnh này vào hàng đợi.

Thường dùng leftist heap hoặc heap ngẫu nhiên để cài đặt heap hợp nhất có thể truy hồi. Bước cuối còn có thể tối ưu hơn: thay vì hợp nhất hai heap con sau khi loại bỏ đỉnh, có thể đưa từng heap con vào hàng đợi riêng biệt, giảm chi phí hợp nhất \(O(\log m)\) mỗi lần. Vì mỗi lần tối đa đưa ba heap mới vào hàng đợi, nên kích thước hàng đợi là \(O(k)\). Như vậy, mỗi lần truy vấn chỉ mất \(O(\log k)\), tổng cộng \(O(k\log k)\).

Vì xây dựng cây đường đi ngắn nhất và heap hợp nhất có thể truy hồi đều \(O(m\log m)\), nên tổng độ phức tạp là \(O(m\log m + k\log k)\).

Cài đặt mẫu

Bài mẫu Library Checker - K-Shortest Walk - Tham khảo cài đặt 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// Submission: https://judge.yosupo.jp/submission/311623
#include <algorithm>
#include <iostream>
#include <queue>
#include <random>
#include <vector>

std::mt19937_64 rng(static_cast<std::mt19937_64::result_type>(time(nullptr)));

constexpr long long inf = 0x3f3f3f3f3f3f3f3f;

// Persistent Randomized Heap.
struct PersistentRandomizedHeap {
  static constexpr int N = 1e7;
  int id;
  std::vector<int> rt, lc, rc, to;
  std::vector<long long> va;

  int new_node(long long cost, int _to) {
    ++id;
    va[id] = cost;
    to[id] = _to;
    return id;
  }

  int copy_node(int x) {
    ++id;
    lc[id] = lc[x];
    rc[id] = rc[x];
    va[id] = va[x];
    to[id] = to[x];
    return id;
  }

  int meld(int x, int y, std::mt19937_64::result_type rand) {
    if (!x || !y) return x | y;
    if (va[x] > va[y]) std::swap(x, y);
    x = copy_node(x);
    if (rand & 1) std::swap(lc[x], rc[x]);
    rc[x] = meld(rc[x], y, rand >> 1);
    return x;
  }

  PersistentRandomizedHeap() : id(0), rt(N), lc(N), rc(N), to(N), va(N) {}

  void insert(int i, long long cost, int _to) {
    rt[i] = meld(rt[i], new_node(cost, _to), rng());
  }

  void merge(int i, int j) { rt[i] = meld(rt[i], rt[j], rng()); }

} heaps;

struct Edge {
  int u, v, c;

  Edge(int u, int v, int c) : u(u), v(v), c(c) {}
};

int n, m, s, t, k;
std::vector<std::vector<int>> gr, ig;
std::vector<Edge> edges;
std::priority_queue<std::pair<long long, int>,
                    std::vector<std::pair<long long, int>>, std::greater<>>
    pq;

std::vector<long long> dist_t;
std::vector<int> out;

// Calculate distances to the destination node t. (Dijkstra)
// Record the optimal outgoing edges which form the shortest path tree T.
void calc_distances_to_t() {
  dist_t.assign(n, inf);
  dist_t[t] = 0;
  out.assign(n, -1);
  pq.emplace(dist_t[t], t);
  while (!pq.empty()) {
    long long di = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    if (di > dist_t[cur]) continue;
    for (auto e : ig[cur]) {
      int nxt = edges[e].u;
      auto di_nxt = di + edges[e].c;
      if (di_nxt < dist_t[nxt]) {
        dist_t[nxt] = di_nxt;
        out[nxt] = e;
        pq.emplace(di_nxt, nxt);
      }
    }
  }
}

// Construct sidetracks and propagate them through tree T.
void build_sidetracks() {
  // Insert all valid sidetracks into heaps.
  for (int i = 0; i < m; ++i) {
    auto edge = edges[i];
    if (out[edge.u] != i && dist_t[edge.u] < inf && dist_t[edge.v] < inf) {
      heaps.insert(edge.u, edge.c + dist_t[edge.v] - dist_t[edge.u], edge.v);
    }
  }
  // Propagate sidetracks down the shortest path tree.
  std::queue<int> q;
  q.push(t);
  while (!q.empty()) {
    auto cur = q.front();
    q.pop();
    for (auto e : ig[cur]) {
      auto nxt = edges[e].u;
      if (out[nxt] == e) {
        heaps.merge(nxt, cur);
        q.push(nxt);
      }
    }
  }
}

std::vector<long long> ans;

// Insert a non-empty heap into the priority queue.
// Total cost is the heap top value adjusted by accumulated cost.
void insert(int x, long long cost) {
  if (x) pq.emplace(cost + heaps.va[x], x);
}

// Find the k shortest paths in the sidetrack graph. (Dijkstra)
// These correspond to the k shortest walks in the original graph.
void find_k_shortest_walks() {
  int cnt = 0;
  ans.assign(k, -1);
  if (dist_t[s] >= inf) return;
  ans[cnt++] = dist_t[s];
  insert(heaps.rt[s], dist_t[s]);
  while (!pq.empty() && cnt < k) {
    auto cost = pq.top().first;
    int cur = pq.top().second;
    pq.pop();
    ans[cnt++] = cost;
    insert(heaps.lc[cur], cost - heaps.va[cur]);
    insert(heaps.rc[cur], cost - heaps.va[cur]);
    insert(heaps.rt[heaps.to[cur]], cost);
  }
}

int main() {
  // Input.
  std::cin >> n >> m >> s >> t >> k;
  gr.resize(n);
  ig.resize(n);
  edges.reserve(m);
  for (int i = 0; i < m; ++i) {
    int u, v, c;
    std::cin >> u >> v >> c;
    edges.emplace_back(u, v, c);
    gr[u].push_back(i);
    ig[v].push_back(i);
  }
  // Calculate.
  calc_distances_to_t();
  build_sidetracks();
  find_k_shortest_walks();
  // Output.
  for (auto x : ans) std::cout << x << '\n';
  return 0;
}

Bài tập

Tài liệu tham khảo & chú thích

Last updated on this page:, Update history
Found an error? Want to help improve? Edit this page on GitHub!
Contributors to this page:OI-wiki
All content on this page is provided under the terms of the CC BY-SA 4.0 and SATA license, additional terms may apply