本科經典算法Dijkstra，被證明是普遍最優了：最壞情況性能也最優！

AIGC動態歡迎閱讀

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

內容摘要：

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

原文鏈接：本科經典算法Dijkstra，被證明是普遍最優了：最壞情況性能也最優！

聯系作者

文章來源：量子位
作者微信：
作者簡介：