“單源最短路徑”問題已解決！

每日分享最新，最流行的軟體開發知識與最新行業趨勢，希望大家能夠一鍵三連，多多支援，跪求關注，點贊，留言。

研究人員開發了一種使用非負邊權重（網路圖中顯示的節點之間的連線）來解決單源最短路徑問題的方法。

網路在當今世界扮演著重要的角色。從防禦到一般通訊，每個垂直社群都透過互連網路相互連線。隨著網路的發展和擴充套件，出現了在該網路中尋找最短通訊路徑的問題。自 1950 年代以來，這一直是網路中的一個重大問題。

哥本哈根大學計算機科學系的研究人員針對這一最短路徑問題開發了一種解決方案。“我們發現了一種演算法，可以在幾乎線性時間內以最快的方式解決問題。這是一個基本的演算法問題，自 1950 年代以來一直在研究，並在世界範圍內教授。這是促使我們解決它的原因之一，”Christian Wulff-Nilsen 副教授解釋說。

單源最短路徑演算法旨在找到從給定起始節點到網路中所有其他節點的最短路徑。網路表示為由節點和它們之間的連線組成的圖，稱為邊。每條邊都有一個方向（例如，這可以用來表示單向道路），以及一個權重，表示沿著該邊行駛的成本。如果所有邊的權重都是非負的，則可以使用經典的 Dijkstra 演算法在幾乎線性時間內解決該問題。

新結果解決問題的時間幾乎與 Dijkstra 演算法相同，但也允許負邊權重。Christian Wulff-Nilsen 說：“原則上，如果投機者正在投機買賣各種貨幣，該演算法可用於警告參與者，例如中央銀行。今天，很多這樣的事情都發生在使用電腦的時候。但由於我們的演算法速度如此之快，它或許可以用於在漏洞被利用之前檢測到漏洞。”

研究人員聲稱，解決單源最短路徑演算法可以讓研究人員建立一種在速度方面幾乎無法超越的極好的演算法。同時，它的簡單性使其易於適應社會的各種需求。

參考資料：Aaron Bernstein 等人，近線性時間中的負權重單源最短路徑，

arXiv

（2022）。 DOI： 10。48550/arxiv。2203。03456