我試圖找到一個直觀的解釋，解釋為什么我們可以推廣 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個最小成本。為什么這是真的？
uj5u.com熱心網友回復：
Wiki 文章沒有具體說明，但該代碼只會解決 k-shortest-paths 的“回圈”版本，其中路徑不需要簡單。
這個問題的簡單路徑版本更難：你會想看看像Yen's algorithm的東西，它在生成路徑時會進行巧妙的過濾以避免重復點。Yen 演算法可以使用 Dijkstra 演算法作為子程式，但也可以使用任何其他最短路徑演算法。
沒有明顯的方法可以修改 Dijkstra 的演算法來解決 k-shortest-simple-paths 問題。您需要跟蹤優先級佇列中的路徑（已在您發布的代碼中完成），但是每個頂點可以被探索的次數有一個指數上限。
在這里，設定一個頂點可以被探索的次數if count[u] <= K的上限，這適用于非簡單路徑的情況。K 1另一方面，直接修改 Dijkstra 的簡單路徑演算法，在最壞的情況下，您需要針對2^(V-1)先前訪問過的節點的每種可能性（或可能稍微小的指數）探索一個節點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/427021.html
上一篇：交替布爾范圍的二維正交加法投影
下一篇：從查找表中確定陣列元素的最快方法