Dijkstra 最短路径生长 · 单源最短路 (源点 s)

💧 把它想成水波扩散:离源头最近的先被淹到、先"定居"(盖章敲定),再从定居点继续往外淹——每步敲定暂定距离最小的顶点,并松弛它的邻边。

顶点sabcdt
距离 d[v]
前驱 π[v]
状态
未淹到(未定) 已定居(敲定) 最短路径树 松弛·改进 松弛·无效 最短路 s→t