它有什么作用?
迪杰斯特拉算法由艾兹赫·迪杰斯特拉于1956年提出,是计算机科学中解决单源最短路径问题的最基本算法之一。它能找出图中从起始顶点到所有其他顶点的最短路径,适用于边权重非负的加权图。
方法背后的直觉
该算法维护一个集合,包含已确定从源点到其最短距离的顶点,并通过迭代选择最近的未处理顶点并更新其邻居的距离来扩展此集合。关键在于贪心性质:一旦一个顶点被选中,其到源点的距离就是最终确定的,因为所有边权重都是非负的,所以任何通过未访问顶点的更长路径都不可能更短。这保证了算法的正确性和最优性。
历史学
艾兹赫·迪杰斯特拉于1959年在一篇三页的论文中发表了他的算法,该论文后来成为计算机科学中引用率最高的研究之一。该算法源于迪杰斯特拉在阿姆斯特丹ARMAC计算机上的工作。数十年来,该算法得到了许多改进,包括更好的数据结构(斐波那契堆实现O(E+VlogV)复杂度)和双向变体。该算法在OSPF等现代网络路由协议中仍然至关重要。
何时使用
在具有非负边权重的图中寻找最短路径时应用迪杰斯特拉算法。它非常适合导航系统、网络路由以及任何需要最优路径的图问题。用于计算到所有顶点的单源最短路径。对于带有负权重的图,应使用贝尔曼-福特算法。对于双向搜索或启发式引导,可以考虑A*算法。
局限与注意事项
- 无法处理带有负边权重的图
- 计算到所有顶点的最短路径,而不仅仅是单个目的地(但可以提前终止)
- 在有可用启发式信息时,效率不如A*
- 需要发现所有顶点;对于非常稀疏的连通性效率不高
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 易于理解和实现,具有明确的正确性保证
- 使用合适的数据结构效率高:二叉堆为O((V+E)logV),数组为O(V²)
- 对非负权重图是最优的;证明了计算路径的最优性
- 可用于有向图和无向图
- 是许多扩展和相关算法的基础
应用
- GPS和导航系统:为车辆和行人寻找最短路线
- 网络路由协议:在计算机网络中确定数据包的最优路径
- 社交网络:寻找用户或影响者之间的最短连接路径
- 游戏开发:为人工智能和非玩家角色移动进行寻路
- 机器人运动规划:为机器人系统计算最优轨迹
- 电信:优化呼叫路由和信号传播路径
使用方式
使用方式
将源点的距离设为零,所有其他顶点的距离设为无穷大。将所有顶点标记为未访问,并创建一个优先队列。
使用优先队列选择从源点到未访问顶点中距离最小的顶点。
对于所选顶点的每个邻居,如果通过所选顶点的路径提供了更短的距离,则更新该邻居的距离并将其加入优先队列。
常见陷阱
- 在带有负权重的图上使用该算法,导致最短路径不正确
- 使用线性时间提取最小操作的低效实现,导致性能不佳
- 在通过不同路径重新访问邻居时未能正确更新距离
常见问题
为什么迪杰斯特拉算法在负权重图上会失败?
该算法假设一旦一个顶点被确定,就无法通过未访问的顶点找到更短的路径。在存在负权重的情况下,一条较长的路径可能在使用了负边之后变得更短,从而违反了这一假设。
优先队列应该使用什么数据结构?
二叉堆在插入和提取操作上都提供O(logV)的复杂度,总复杂度为O((V+E)logV)。斐波那契堆可达到O(E+VlogV),但常数因子较大。对于小型图,数组也是可行的。
迪杰斯特拉算法如何找到到单个特定目的地的路径?
在目标顶点被选中(其距离被确定)时立即终止算法,避免不必要的计算。或者,在执行过程中维护父指针来重建路径。
迪杰斯特拉算法能否用于无向图?
可以,无向图可以表示为有向图,其中每条无向边在两个方向上都有对应的有向边,且权重相同。算法在双向表示上工作方式相同。
相关方法
参考文献
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
打开 DOI 文献已复制。Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN:978-0-262-03384-8已复制。