为什么修改Dijkstra算法可以找到K条最短路径？

Question

我试图找到一个直观的解释，说明为什么我们可以推广 Dijkstra 算法以在没有负边的有向加权图中从单个源找到 K 条最短（简单）路径。根据维基百科，修改后的Dijkstra伪代码如下：

Definitions:
  G(V, E): weighted directed graph, with set of vertices V and set of directed edges E,
  w(u, v): cost of directed edge from node u to node v (costs are non-negative).
  Links that do not satisfy constraints on the shortest path are removed from the graph
  s: the source node
  t: the destination node
  K: the number of shortest paths to find
  P[u]: a path from s to u
  B: a heap data structure containing paths
  P: set of shortest paths from s to t
  count[u]: number of shortest paths found to node u

Algorithm:
  P = empty
  for all u in V:
    count[u] = 0
  insert path P[s] = {s} into B with cost 0

  while B is not empty:
    let P[u] be the shortest cost path in B with cost C
    remove P[u] from B
    count[u] = count[u] + 1
    
    if count[u] <= K then:
      for each vertex v adjacent to u:
        let P[v] be a new path with cost C + w(u, v) formed by concatenating edge (u, v) to path P[u]
        insert P[v] into B
  return P

我知道，对于原始的Dijkstra算法，可以通过归纳证明，当一个节点被添加到闭集时（或者如果以BFS +堆的形式实现，则从堆中弹出），成本从源到该节点必须最小。

这里的算法似乎是基于这样一个事实，即当一个节点从堆中弹出第 i^th 次时，我们有第 i^th 从源头到它的最小成本。为什么是这样？

Answer 1

Wiki 文章没有具体说明，但该代码只会解决 'loopy' 版本的 k-shortest-paths，其中路径不需要简单。

问题的简单路径版本更难：您需要查看类似 Yen's algorithm 的内容，它会进行巧妙的过滤以避免在生成路径时重复点。 Yen的算法可以使用Dijkstra的算法作为子程序，但也可以使用任何其他shortest-path算法代替。

没有明显的方法可以修改 Dijkstra 算法来解决 k-shortest-simple-paths 问题。您需要跟踪优先级队列中的路径（这已经在您发布的代码中完成），但是每个顶点可以被探索的次数有一个指数上限。

这里，if count[u] <= K 对一个顶点的探索次数设置了 K+1 的上限，这适用于 non-simple 路径情况。另一方面，在最坏的情况下，直接修改简单路径的 Dijkstra 算法将要求您针对先前访问过的节点的每个 2^(V-1) 可能性探索一次节点（或者可能稍微较小的指数）。

为什么修改Dijkstra算法可以找到K条最短路径？

Why can Dijkstra's Algorithm be modified to find K shortest paths?

algorithm

shortest-path