「在一個(gè)帶權(quán)有向圖G=(V,E)中，每條邊的權(quán)是一個(gè)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。

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

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

負(fù)權(quán)值SSSP算法：速度快、效率高

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

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

關(guān)于SSSP有兩個(gè)經(jīng)典算法：Dijkstra算法（迪克斯特拉算法）和Bellman-Ford算法（貝爾曼-福特算法），兩者都有各自的局限性。

Dijkstra算法運(yùn)算時(shí)間最短，能達(dá)到近線性時(shí)間 O(m + n log n) ，但不能計(jì)算負(fù)權(quán)值邊。

Bellman-Ford算法可以計(jì)算負(fù)權(quán)值邊，但運(yùn)算時(shí)間過長，達(dá)到O(mn)。目前，最頂尖的解決負(fù)權(quán)邊的SSSP算法都依賴于復(fù)雜的連續(xù)優(yōu)化和動(dòng)態(tài)代數(shù)和圖形算法。這就導(dǎo)致即使后世學(xué)者不斷優(yōu)化該算法，其運(yùn)算時(shí)間仍需?(n(4/3) log W)。這個(gè)運(yùn)算時(shí)間的約束已經(jīng)存在三十年之久。

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

1）帶負(fù)權(quán)邊算法的運(yùn)算能否達(dá)到近線性時(shí)間？

2）能否用簡單的工具達(dá)到這個(gè)目的？

有沒有一種方法，可以既要時(shí)間，又要質(zhì)量呢？

別說，還真有。

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

推導(dǎo)過程

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

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

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

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

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

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

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

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

如果G是一個(gè)DAG（有向無環(huán)圖），計(jì)算一個(gè)價(jià)格函數(shù)Φ，使具有非負(fù)權(quán)邊是很簡單的：只需在拓?fù)涞膙1, ..., vn上循環(huán)，并設(shè)置Φ(vi)，使所有進(jìn)入的邊權(quán)值為非負(fù)。

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

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

每條邊都有一個(gè)方向（例如，這可用于表示單向道路）以及一個(gè)權(quán)重，用于表示沿該邊行駛的成本。如果所有邊權(quán)重都是非負(fù)的，則可以使用經(jīng)典的Dijkstra算法在幾乎線性的時(shí)間內(nèi)解決問題。

新結(jié)果在與Dijkstra算法幾乎相同的時(shí)間內(nèi)解決了這個(gè)問題，但也允許負(fù)邊權(quán)重。

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

ScaleDown算法分階段運(yùn)行，在最后一個(gè)階段它用ElimNeg（）來計(jì)算價(jià)格函數(shù)Φ2。如果ElimNeg終止，它將返回價(jià)格函數(shù)ψ′，讓所有邊值非負(fù)；換句話說，因?yàn)?/span>，所以中不包含負(fù)權(quán)值。

這意味著，對于所有，都滿足條件（因?yàn)?img src="https://s5.51cto.com/oss/202211/28/353d1488122478f0ae8338c426a9ca22b09e11.png" alt="圖片" title="圖片" style="visibility: visible; width: 306px; height: 59px;" data-type="inline">）。由此證明了 ScaleDown輸出的正確性。

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

這意味著對于所有，。因此圖形G*具有非負(fù)權(quán)值。

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

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

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

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

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

至此，Wulff-Nilsen的負(fù)權(quán)值SSSP解決方案中最重要的兩個(gè)算法均證明成立。新算法在保證近線性時(shí)間的同時(shí)，成功引入了負(fù)權(quán)值。?

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

去年，Wulff-Nilsen在同一領(lǐng)域取得了另一項(xiàng)突破，結(jié)果涉及如何在隨時(shí)間變化的網(wǎng)絡(luò)中找到最短路徑。他對最近謎語的解決方案建立在這項(xiàng)工作的基礎(chǔ)上。

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

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

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

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

或許，這就是科學(xué)的魅力吧。