<2> 从U中选出”距离最短的顶点k”,并将顶点k加入到S中;同时,
从U中移除顶点k。
<3> 更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离,
是由于上一步中确定了k是求出最短路径的顶点,从而可以利用k来更新
其它顶点的距离;例如,(s,v)的距离可能大于(s,k)+(k,v)的距离。
<4> 重复步骤(2)和(3),直到遍历完所有顶点。
<1>在有向图中选一个没有直接前驱的顶点,并输出之;
<2>从图中删去该顶点, 同时删去所有它发出的有向边;
重复以上步骤,直到全部顶点均已输出,拓扑有序序列形成,拓扑
排序完成;或图中还有未输出的顶点,但已跳出处理循环。这说明图中
还剩下一些顶点,它们都有直接前驱,再也找不到没有前驱的顶点了。
这时有向图中必定存在有向环。