Thorups 演算法

用於無向圖的單源最短路徑的 Thorup 演算法具有時間複雜度 O(m)，低於 Dijkstra。

基本思路如下。 （對不起，我還沒有嘗試實現它，所以我可能會錯過一些小細節。原始論文是支付給我的，所以我試圖從引用它的其他來源重建它。如果你可以驗證，請刪除這個評論。）

• 有辦法在 O(m) 中找到生成樹（此處未描述）。你需要將生成樹從最短邊緣增長到最長邊，並且在完全成長之前它將是具有多個連線元件的森林。
• 選擇一個整數 b（b> = 2）並僅考慮長度限制為 b ^ k 的生成林。合併完全相同但具有不同 k 的元件，並將元件的級別稱為最小 k。然後在邏輯上將元件製作成樹。如果 u 是與 v 完全包含 v 的最小元件，則 u 是 v 的父項。根是整個圖形，葉子是原始圖形中的單個頂點（負無窮大級別）。樹仍然只有 O(n) 個節點。
• 保持每個元件到源的距離（如 Dijkstra 演算法）。具有多個頂點的元件的距離是其未展開的子項的最小距離。將源頂點的距離設定為 0 並相應地更新祖先。
• 考慮基數 b 的距離。當第一次訪問級別 k 中的節點時，將其子節點放入由級別 k 的所有節點共享的桶中（如在桶排序中，將 Dijkstra 演算法中的堆替換為數字 k 及其距離的更高）。每次訪問節點時，只考慮其第一個桶，訪問並刪除每個桶，更新當前節點的距離，並使用新距離將當前節點重新連結到其父節點，並等待下一次訪問以下桶。
• 當訪問葉子時，當前距離是頂點的最終距離。展開原始圖形中的所有邊緣並相應地更新距離。
• 重複訪問根節點（整個圖形），直到到達目的地。

它基於以下事實：在生長森林的兩個連線元件之間沒有長度小於 l 的邊緣，長度限制為 l，因此，從距離 x 開始，你可以只關注一個連線的元件，直到達到距離 x + l。在訪問具有較短距離的頂點之前，你將訪問一些頂點，但這並不重要，因為已知從這些頂點到此處不會有更短的路徑。其他部分的工作類似於桶排序/ MSD 基數排序，當然，它需要 O(m) 生成樹。