k短路

What · 是什么

k 短路问题：求从 s 到 t 的第 k 短路径长度（允许重复经过边/点，即『途径』k-shortest walk）。主流方法：① A* 搜索：用反向图上到 t 的最短路作为启发函数 h，状态 (g(x), x) 以 f=g+h 为优先级出队，第 k 次弹到 t 即为第 k 短；② Eppstein 的可持久化可并堆法：按最短路树上的『偏离边』建立 k 短路径偏序，预处理后 O(log n + k log n) 逐条输出，是严格多项式最坏界方法。竞赛模板题常用 A*（实现简单、k 较小可行）。

Why · 为什么

How · 实现

伪代码

# A* 版 (正权图)
def kth_shortest(n, adj, radj, s, t, k):
  h = dijkstra_on_reverse(radj, t)   # h[x]=x到t最短路
  pq = [(h[s], 0, s)]                 # (f, g, node)
  cnt = [0]*n
  while pq:
    f, g, u = heappop(pq)
    cnt[u] += 1
    if u == t and cnt[u] == k: return g
    if cnt[u] > k: continue
    for v, w in adj[u]:
      heappush(pq, (g + w + h[v], g + w, v))
  return -1

Python 实现

import heapq


def kth_shortest_astar(n, adj, radj, s, t, k):
    """A* 求第 k 短路径长度 (允许重复走边; 正权图).
    adj: 正向邻接表; radj: 反向邻接表."""
    INF = float('inf')
    # 1) 反向 Dijkstra 求 h[x] = x 到 t 的最短路
    h = [INF] * n
    h[t] = 0
    pq = [(0, t)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > h[u]:
            continue
        for v, w in radj[u]:
            nd = d + w
            if nd < h[v]:
                h[v] = nd
                heapq.heappush(pq, (nd, v))

    # 2) A* 扩展
    cnt = [0] * n
    pq = [(h[s], 0, s)]  # (f=g+h, g, node)
    while pq:
        f, g, u = heapq.heappop(pq)
        cnt[u] += 1
        if u == t and cnt[u] == k:
            return g
        if cnt[u] > k:
            continue
        for v, w in adj[u]:
            if h[v] == INF:
                continue
            heapq.heappush(pq, (g + w + h[v], g + w, v))
    return -1  # 不足 k 条


if __name__ == "__main__":
    # 小型图
    n = 4
    adj = [[] for _ in range(n)]
    radj = [[] for _ in range(n)]
    edges = [(0, 1, 1), (1, 2, 1), (2, 3, 1), (0, 2, 3), (0, 3, 10), (1, 3, 5)]
    for u, v, w in edges:
        adj[u].append((v, w))
        radj[v].append((u, w))
    # 0->3 的所有路径长度: 0-3=10; 0-1-3=6; 0-2-3=4; 0-1-2-3=3
    # 排序: 3, 4, 6, 10, 且允许重复绕圈 (无穷多条)
    got = [kth_shortest_astar(n, adj, radj, 0, 3, k) for k in (1, 2, 3, 4)]
    assert got == [3, 4, 6, 10], got

    # 枚举验证前 4 条 (小图直接枚举路径)
    import random
    random.seed(61)

    def brute_k(n, adj, s, t, k, cap_len=8):
        res = []
        def dfs(u, d, steps):
            if u == t:
                res.append(d)
            if steps >= cap_len:
                return
            for v, w in adj[u]:
                dfs(v, d + w, steps + 1)
        dfs(s, 0, 0)
        res.sort()
        return res[k - 1] if len(res) >= k else -1

    for _ in range(60):
        n = random.randint(2, 6)
        adj = [[] for _ in range(n)]
        radj = [[] for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i != j and random.random() < 0.35:
                    w = random.randint(1, 5)
                    adj[i].append((j, w))
                    radj[j].append((i, w))
        k = random.randint(1, 4)
        a = kth_shortest_astar(n, adj, radj, 0, n - 1, k)
        b = brute_k(n, adj, 0, n - 1, k)
        # 允许重复走边时 A* 会得到无穷多条; 只当枚举 cap 覆盖时比较
        if b != -1:
            assert a == b, (n, k, a, b)
    print("All tests passed.")

易错点

• A* 弹出 t 第 k 次才是第 k 短——不能一弹到 t 就终止
• 负权图：h 需先用势能法处理（Bellman-Ford 求 h 再 A*）
• 『简单路径』k 短路与『途径』k 短路是不同问题，题面要看清
• k 很大时 A* 状态爆炸，应换 Eppstein/删边法
• 重边/环导致无穷多条路径，答案可能含重复绕圈，注意题面约定
• h[v]==INF（v 到不了 t）的节点不能入队

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/kth-path/
• CP-Algorithms△ https://cp-algorithms.com/graph/kth-shortest-path.html
• web✓ https://en.wikipedia.org/wiki/K_shortest_path_routing