本科經(jīng)典算法Dijkstra，被證明是普遍最優(yōu)了：最壞情況性能也最優(yōu)！

AIGC動態(tài)歡迎閱讀

原標題：本科經(jīng)典算法Dijkstra，被證明是普遍最優(yōu)了：最壞情況性能也最優(yōu)！
關鍵字：算法,路徑,距離,數(shù)據(jù)結構,計算機
文章來源：量子位
內(nèi)容字數(shù)：0字

內(nèi)容摘要：

金磊發(fā)自凹非寺量子位 | 公眾號 QbitAI時隔近70年，那個用來解決最短路徑問題的經(jīng)典算法——Dijkstra，現(xiàn)在有了新突破：
被證明具有普遍最優(yōu)性（Universal Optimality）。
什么意思？
這就意味著不論它面對多復雜的圖結構，即便在最壞情況下都能達到理論上的最優(yōu)性能！
而且這還是學術界首次將這一概念應用于任何序列算法。
△圖源：Quantamagzine對于Dijkstra算法，想必很多人肯定不會陌生，畢竟它是每個計算機本科生必學的內(nèi)容。
而且從它誕生至今，已經(jīng)在廣泛地應用于我們的日常生活中，例如在谷歌地圖、蘋果地圖，Dijkstra算法就被用來計算從用戶當前位置到目的地的最優(yōu)路線。
在計算機網(wǎng)絡中，被廣泛應用于路由協(xié)議中；例如開放最短路徑優(yōu)先（OSPF）協(xié)議就是基于Dijkstra算法來計算網(wǎng)絡中數(shù)據(jù)包的最優(yōu)傳輸路徑。
再如通信網(wǎng)絡設計、機器人路徑規(guī)劃和物流運輸優(yōu)化等領域，也是處處都有它的身影。
（相關教程可參考：https://www.youtube.com/watch?v=EFg3u_E6eHU）
而這項集結了蘇黎世聯(lián)邦理工、CMU、普林斯頓等頂尖高校

原文鏈接：本科經(jīng)典算法Dijkstra，被證明是普遍最優(yōu)了：最壞情況性能也最優(yōu)！