输出:
得到从源点到剩下所有节点的最短路径信息....此时v2列还无法确认是真,因为有可能从更近的v1出去再到达v2的某条路径更短.所以我接下来一个动作是从v1发散到v1所有的邻居并更新min表....CPU查看MAP时发现v1可到达v2,v3和v4.v0就不用去了,第一是环路,第二v0列已经是真,无法再刷新该字段.由此v0通过v1到达v2,v3和v4的开销为3+1,7+1,5+1.然后刷新min表:...,v4和v5中选择最小的v4,v4列为真,原因不再赘述,标为红色如表.再发散v4刷新v3v5v6v7:
min v0 v1 v2 v3 v4 v5 v6 v7 v8
v0 0 1 4 8 5 11 ∞...于是最后得到的拓展min表是这样的:
min v0 v1 v2 v3 v4 v5 v6 v7 v8
v0 0 1 4 7 5 8 10 12 16
min v0 v1 v2 v3 v4 v5 v6 v7