我试图找到一个直观的解释,说明为什么我们可以推广 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小的成本。为什么这是真的呢?