本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！

AIGC动态欢迎阅读

原标题：本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！
关键字：算法,路径,距离,数据结构,计算机
文章来源：量子位
内容字数：0字

内容摘要：

金磊 发自 凹非寺量子位 | 公众号 QbitAI时隔近70年，那个用来解决最短路径问题的经典算法——Dijkstra，现在有了新突破：
被证明具有普遍最优性（Universal Optimality）。
什么意思？
这就意味着不论它面对多复杂的图结构，即便在最坏情况下都能达到理论上的最优性能！
而且这还是学术界首次将这一概念应用于任何序列算法。
△图源：Quantamagzine对于Dijkstra算法，想必很多人肯定不会陌生，毕竟它是每个计算机本科生必学的内容。
而且从它诞生至今，已经在广泛地应用于我们的日常生活中，例如在谷歌地图、苹果地图，Dijkstra算法就被用来计算从用户当前位置到目的地的最优路线。
在计算机网络中，被广泛应用于路由协议中；例如开放最短路径优先（OSPF）协议就是基于Dijkstra算法来计算网络中数据包的最优传输路径。
再如通信网络设计、机器人路径规划和物流运输优化等领域，也是处处都有它的身影。
（相关教程可参考：https://www.youtube.com/watch?v=EFg3u_E6eHU）
而这项集结了苏黎世联邦理工、CMU、普林斯顿等顶尖高校

原文链接：本科经典算法Dijkstra，被证明是普遍最优了：最坏情况性能也最优！

联系作者

文章来源：量子位
作者微信：
作者简介：