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

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

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

內(nèi)容摘要：

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

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