Dijkstra算法計算N條最短路徑

Question

是否有可能使用Dijkstra's Algorithm來計算從單個源到單個目的地的N條最短路徑，其中N是節點數？我知道Dijkstra輸出從單一來源到圖表中所有節點的最短路徑，但是在我閱讀研究論文時，作者提到使用Dijkstra來計算s和t之間的N條最短路徑，並且我困惑了一下。

以下是從原來的紙報價： 善用基於SDN SCADA系統：還發現了一個防竊聽的案例研究here

Dijkstra算法[22]是用來計算N個最短路線（步驟5），分N個階段。考慮到N = 2，在第一階段，Dijkstra算法確定了兩個網絡設備之間的最短路徑，隨後所有鏈路成本的權重都增加了十倍。緊接着，在第二階段（並且鏈接成本增加）之後，再次執行Dijkstra的算法以返回第二短的路線。最後，在第二階段，第一路線的鏈路成本也重新建立到原始值。如後面所解釋的，所述N個最短路線將被用於遞送使用不同的路徑，並且基於這個原因的通信流，它們被存儲到在之後使用

Answer 1

的N這裏似乎是一個參數的作者控制，不特定於圖遍歷算法。他們使用該算法找到源和目標站之間的最短路徑。

接下來，算法 計算主站和 特定變電站之間的N個最短的路線，...

N是級數。他們這樣做一次，找到最短路徑，並在鏈接上增加成本（乘以10）。然後，他們再次運行算法以更新新的鏈接成本，找到第二短的（最少成本）路徑，依此類推，N次。

然後在最後他們將鏈接成本重置爲其原始值。

它們不描述一些奇特的N-對最短路徑，而僅僅是相同的經典最短路徑between- s - 和 - t算法N時間（在每個運行不同的鏈路成本）的一個應用程序。其他

變體

上this引用維基百科：

該算法在許多變種存在; Dijkstra的原始變體找到了兩個節點之間的最短路徑[2]，但更常見的變體將單個節點修復爲「源」節點，並找到從源到圖中所有其他節點的最短路徑，從而生成最短路徑樹。

你可以使用Dijkstra的一個運行從一個選定的源節點到所有其他節點的最短路徑計算，但在紙的情況下在這裏，它相同的源（主站）和目的地之間總是（變電站）。