§06 图状结构
最短路径
Dijkstra 算法求解单源最短路径：每轮确定一个距离已最小（dist）的顶点，再用它松弛全部 出边，不断修正其余顶点的 dist。顶点下方的数字实时显示当前 dist，深色边构成最短路径树。
最短路径
伪代码
1
procedure Dijkstra(G, v0)
2
dist[v0] ← 0; 其余顶点 dist[v] ← ∞
3
S ← empty set // 已确定最短路径的顶点
4
while S ≠ V do
5
u ← dist 最小且 ∉ S 的顶点
6
S ← S ∪ {u} // 确定 u 的最短路径
7
for each 出边 (u, v, w) do
8
if dist[u] + w < dist[v] then
9
dist[v] ← dist[u] + w // 松弛成功，更新 v
10
end while
11
end procedure