「在一個帶權有向圖G=(V,E)中，每條邊的權是一個實數。另外，還給定V中的一個頂點，稱為源。

計算從源到其他所有各頂點的最短路徑長度，這就是單源最短路徑（SSSP）問題。」

半個多世紀以來，世界各地的研究人員一直在努力解決這個問題。而現在，該算法謎題終于被哥本哈根大學計算機科學系的研究團隊成功解決。

負權值SSSP算法：速度快、效率高

論文鏈接：https://arxiv.org/abs/2203.03456

接受采訪時，研究人員Christian Wulff-Nilsen稱，他們的解決方案是第一個突破存在30多年的?(n(4/3) log W)運算時間約束的，帶有負權值的SSSP組合算法。

關于SSSP有兩個經典算法：Dijkstra算法（迪克斯特拉算法）和Bellman-Ford算法（貝爾曼-福特算法），兩者都有各自的局限性。

Dijkstra算法運算時間最短，能達到近線性時間 O(m + n log n) ，但不能計算負權值邊。

Bellman-Ford算法可以計算負權值邊，但運算時間過長，達到O(mn)。目前，最頂尖的解決負權邊的SSSP算法都依賴于復雜的連續優化和動態代數和圖形算法。這就導致即使后世學者不斷優化該算法，其運算時間仍需?(n(4/3) log W)。這個運算時間的約束已經存在三十年之久。

面對這些局限，Wulff-Nilsen提出了兩個問題：

1）帶負權邊算法的運算能否達到近線性時間？

2）能否用簡單的工具達到這個目的？

有沒有一種方法，可以既要時間，又要質量呢？

別說，還真有。

Wulff-Nilsen提出的算法為圖像縮放算法，被簡易圖像分解算法Low Diameter Decomposition強化。通常情況，該分解算法只用于非負權邊的圖形分解，而該研究的貢獻之一就在于將其運用到負權邊圖像中，加強負權邊SSSP遞歸縮放算法。

推導過程

Wulff-Nilsen以Johnson的價格算法為基礎。提出：在圖像G = (V, E, w)中，令Φ為任意函數：V→Z。令w(Φ)為權函數：

定義：，則：。在圖像G = (V, E,w)和圖像G' = (V, E,w')中，若：1）圖像G中的最短距離與圖像G’中的最短距離相等，反之亦然；2）G只在G'含有負權環時含有負權環，則圖像G與圖像G'相等。

推論2.7考慮到任意圖像和價格函數Φ。在 u, v ∈ V 中，

。而在任意環C中，

。因此，G和相等。如果，，那么G和G'相等。

該算法的目的是在計算價格函數Φ時，在GΦ中的所有邊權都為非負，假設不存在負權環。之后就可以在上運行Dijkstra算法。

之后，Wulff-Nilsen開始介紹自己的算法框架。

首先，Wulff-Nilsen假設存在一種算法 Dijkstra（G,s），輸入無負權邊的圖形G，頂點s ∈ V，G中的s輸出最短路徑樹。運行時間為O(m + n log n)。

如果G是一個DAG（有向無環圖），計算一個價格函數Φ，使具有非負權邊是很簡單的：只需在拓撲的v1, ..., vn上循環，并設置Φ(vi)，使所有進入的邊權值為非負。

單源最短路徑問題的目的是找到從給定起始節點到網絡中所有其他節點的最短路徑。

網絡表示為由節點和它們之間的連接組成的圖形，稱為邊。

每條邊都有一個方向（例如，這可用于表示單向道路）以及一個權重，用于表示沿該邊行駛的成本。如果所有邊權重都是非負的，則可以使用經典的Dijkstra算法在幾乎線性的時間內解決問題。

新結果在與Dijkstra算法幾乎相同的時間內解決了這個問題，但也允許負邊權重。

之后，Wulff-Nilsen提到了組合工具中最重要的兩個算法：ScaleDown和SPmain。

ScaleDown算法分階段運行，在最后一個階段它用ElimNeg（）來計算價格函數Φ2。如果ElimNeg終止，它將返回價格函數ψ′，讓所有邊值非負；換句話說，因為，所以中不包含負權值。

這意味著，對于所有，都滿足條件（因為）。由此證明了 ScaleDown輸出的正確性。

如果算法終止，則對于所有和，是積分，并且對于所有，。

這意味著對于所有，。因此圖形G*具有非負權值。

通過歸納法，假設該理論適用于，算法第5行中對ScaleDown的調用滿足必要的輸入屬性。

因此，通過和ScaleDown的Output，可以得到。

由于，若令C為中任意負權環，由于中的所有權值都為2n的倍數，且；又知，故與推論2.7不符。

從而得出結論：如果包含負權環，則算法不會終止。

由此可以證明，SPmain算法的正確性。

至此，Wulff-Nilsen的負權值SSSP解決方案中最重要的兩個算法均證明成立。新算法在保證近線性時間的同時，成功引入了負權值。?

60年后，尋求答案不僅為了解謎

去年，Wulff-Nilsen在同一領域取得了另一項突破，結果涉及如何在隨時間變化的網絡中找到最短路徑。他對最近謎語的解決方案建立在這項工作的基礎上。

他認為，解決SSSP問題可以為算法鋪平道路，不僅可以幫助電動汽車立即計算到達目的地的最快路線，而且能保證以最節能的方式做到這一點。

Wulff-Nilsen解釋道：“我們的算法里加入了負權這個以前算法沒有的維度。一個實際的例子是在山間駕駛時，有了負權這一維度，導航系統可以為電動車車主推薦下坡路多的路線，使電動車可以在下坡時進行充電。”

Wulff-Nilsen還表示，他們的算法不僅可以用于電動車路線規劃，還能用于監測金融業的投機行為。他說：“原則上，該算法可以用來為中央銀行等用戶預警，警告投機者在投機買賣各種貨幣。現在，很多不法之徒利用計算機犯罪，但由于我們的算法如此之快，或許能夠被用來監測，在人們利用漏洞之前及時發現。”

1959年，當Dijkstra首次提出最短距離問題時，可能他也不會想到，60多年來，一直有人不斷優化這一問題的方案。或許也會驚訝，謎題的答案竟然有如此豐富的內涵。

或許，這就是科學的魅力吧。