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

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

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

負權值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算法都依賴于復雜的連續(xù)優(yōu)化和動態(tài)代數和圖形算法。這就導致即使后世學者不斷優(yōu)化該算法，其運算時間仍需?(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'含有負權環(huán)時含有負權環(huán)，則圖像G與圖像G'相等。

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

。而在任意環(huán)C中，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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