Dijkstra 最短路径生长 ·
单源最短路 (源点 s)
💧 把它想成
水波扩散
:离源头最近的先被淹到、先"定居"(盖章敲定),再从定居点继续往外淹——每步敲定暂定距离最小的顶点,并松弛它的邻边。
💧
记住
:水波先淹到谁,谁的路就最短——
每步"盖章"暂定距离最小的点(贪心),再松弛它的邻边
。本图最短路
s→a→b→c→t,总长 7
。
顶点
s
a
b
c
d
t
距离 d[v]
前驱 π[v]
状态
未淹到(未定)
已定居(敲定)
最短路径树
松弛·改进
松弛·无效
最短路 s→t
⟲ 重置
‹ 上一步
下一步 ›
▶ 自动播放