为什么可以修改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次弹出时，我们有源节点到该节点的第i小的成本。为什么这是真的呢？

- dw218192

Answer 1

维基百科的文章没有明确说明，但是该代码只能解决“循环”的k短路问题，其中路径不需要是简单的。

问题的简单路径版本更难：您需要查看类似于Yen算法的东西，该算法在生成路径时进行巧妙的过滤以避免重复点。 Yen算法可以使用Dijkstra算法作为子程序，但也可以使用任何其他最短路径算法。

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

这里，如果 count[u] <= K，则对于非简单路径情况，会将一个顶点被探索的次数上限设为 K+1。另一方面，对于简单路径，直接修改 Dijkstra 算法在最坏情况下需要探索每个节点，因为有2^(V-1)种可能性，即哪些节点之前已经被访问过（或者可能是稍微小一些的指数）。

- kcsquared