7.2 Dijkstra 算法要解决的问题与几何直观

liweiwei1419 ... 2021-12-11 图论
  • Dijkstra
Less than 1 minute

# Dijkstra 算法要解决的问题

  • 带权图的最短路径问题;
  • 有向和无向均适用;
  • 前提:没有负权边。

解决没有负权边的单源最短路径问题:即从一个顶点出发到其它顶点的最短路径。

说明:这个例子来自于 liuyubobobo 老师在慕课网上开设的课程 算法与数据结构-综合提升 C++版 (opens new window) ,选择这个例子是因为它足够简单,能够把 Dijkstra 算法的思想说清楚。

# 几何直观

  • 理解源点,我们这里讲解的例子都认为 0 是源点;
  • 把源点从水平平面上拉起来,形成下面的图形。

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

Last update: January 14, 2022 10:18
Contributors: suanfa8 , liweiwei1419