网络延迟时间

记住这句，下面每一帧都在套它。

源点是节点 1：到自己的距离 dist=0，其余节点先记成 ∞（还不知道怎么到）。

当前未确定的节点里，dist 最小的是节点 1（dist=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。

当前未确定的节点里，dist 最小的是节点 2（dist=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。

当前未确定的节点里，dist 最小的是节点 3（dist=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。

当前未确定的节点里，dist 最小的是节点 4（dist=5）。取出它——它的最短距离从此确定。

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

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

当前未确定的节点里，dist 最小的是节点 5（dist=6）。取出它——它的最短距离从此确定。

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

当前未确定的节点里，dist 最小的是节点 6（dist=8）。取出它——它的最短距离从此确定。

所有节点都确定了。最大的 dist 是 8（节点最远的那个），就是信号传遍全网要的时间 → 答案 8。

边界先想清。

两个高频追问。