网络延迟时间

非负边权保证后续路径不能把当前最小距离再缩短，因此这个节点的距离可以确定。

源点距离为 0，其他节点为 ∞。列表仅展示各未确定节点的当前最短距离，不展示堆中的过期记录。

未确定节点中，节点 1 的当前距离 0 最小，确定它的最短距离。接着检查它的出边。

松弛 1→2：经过 1 走，dist[1]+2=2，比原来的 ∞ 更近 → 更新 dist[2]=2。

松弛 1→3：经过 1 走，dist[1]+5=5，比原来的 ∞ 更近 → 更新 dist[3]=5。

松弛 1→4：经过 1 走，dist[1]+9=9，比原来的 ∞ 更近 → 更新 dist[4]=9。

未确定节点中，节点 2 的当前距离 2 最小，确定它的最短距离。接着检查它的出边。

松弛 2→3：经过 2 走，dist[2]+1=3，比原来的 5 更近 → 更新 dist[3]=3。

松弛 2→4：经过 2 走，dist[2]+4=6，比原来的 9 更近 → 更新 dist[4]=6。

松弛 2→5：经过 2 走，dist[2]+8=10，比原来的 ∞ 更近 → 更新 dist[5]=10。

未确定节点中，节点 3 的当前距离 3 最小，确定它的最短距离。接着检查它的出边。

松弛 3→4：经过 3 走，dist[3]+2=5，比原来的 6 更近 → 更新 dist[4]=5。

松弛 3→5：经过 3 走，dist[3]+3=6，比原来的 10 更近 → 更新 dist[5]=6。

松弛 3→6：经过 3 走，dist[3]+9=12，比原来的 ∞ 更近 → 更新 dist[6]=12。

未确定节点中，节点 4 的当前距离 5 最小，确定它的最短距离。接着检查它的出边。

松弛 4→5：经过 4 走是 5+1=6，不比现有的 6 近 → 不更新。

松弛 4→6：经过 4 走，dist[4]+6=11，比原来的 12 更近 → 更新 dist[6]=11。

未确定节点中，节点 5 的当前距离 6 最小，确定它的最短距离。接着检查它的出边。

松弛 5→6：经过 5 走，dist[5]+2=8，比原来的 11 更近 → 更新 dist[6]=8。

未确定节点中，节点 6 的当前距离 8 最小，确定它的最短距离。接着检查它的出边。

最短距离依次为 0、2、3、5、6、8。最晚收到信号的节点是 6，因此答案为 8。

补充例子：从节点 1 出发，堆先保存记录 1(0)。括号内是入堆时的距离。

扩展节点 1，得到到节点 2 的距离 5、到节点 3 的距离 1，分别入堆。

弹出 3(1)，沿 3→2 得到 1+1=2，更新 dist[2]。旧记录 2(5) 仍留在堆里。

弹出 2(2)，它与 dist[2] 相等。节点 2 没有出边，继续取下一条记录。

弹出旧记录 2(5)。5 大于 dist[2]=2，跳过它，不再检查出边。最终答案为 2。

不可达例子：源点改为 2，但唯一边为 1→2。节点 2 没有出边。

堆已经为空，节点 1 的距离仍为 ∞，所以返回 -1。

单个源点不需要传播时间；有向边只能沿箭头传播，不能从终点反向到起点。

选择数据结构前，先检查边权条件与图的规模。线性扫描和堆实现的取舍不同。