教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

Dijkstra最短路径算法

介绍

Dijkstra算法是一种解决带权图中单源最短路径问题的贪心算法,该算法从一个起始顶点出发,逐步确定到图中所有其他顶点的最短路径。与广度优先搜索不同,Dijkstra算法可以处理带权图,特别是当所有边的权重为非负值时,能够找到从起始顶点到图中任意顶点的最短路径。

算法步骤

  1. 创建一个距离数组dist[],对于每个顶点v,初始化dist[v]为无穷大,但起始顶点s的距离为0
  2. 创建一个集合S,用于存储已找到最短路径的顶点,初始为空
  3. 循环重复以下步骤,直到所有顶点都被加入集合S:
    • 选择不在S中且距离值最小的顶点u
    • 将顶点u加入集合S
    • 更新u的所有邻接顶点v的距离值:如果dist[u] + w(u,v) < dist[v],则更新dist[v] = dist[u] + w(u,v)
  4. 当循环结束时,dist[]数组包含了从起始顶点s到所有其他顶点的最短距离

算法详解

以共有6个顶点(0-5)的带权有向图为例,边的权重如下:

  • (0,1):权重5
  • (0,2):权重2
  • (1,3):权重4
  • (1,4):权重2

...

目录