7.2 Dijkstra 算法要解决的问题与几何直观
liweiwei1419 ... 2021-12-11 Less than 1 minute
# Dijkstra 算法要解决的问题
- 带权图的最短路径问题;
- 有向和无向均适用;
- 前提:没有负权边。
解决没有负权边的单源最短路径问题:即从一个顶点出发到其它顶点的最短路径。
说明:这个例子来自于 liuyubobobo 老师在慕课网上开设的课程 算法与数据结构-综合提升 C++版 (opens new window) ,选择这个例子是因为它足够简单,能够把 Dijkstra 算法的思想说清楚。
# 几何直观
- 理解源点,我们这里讲解的例子都认为
0
是源点; - 把源点从水平平面上拉起来,形成下面的图形。

说明:这些弯曲的边,都是被「松弛操作」淘汰的边。