《图论动画-Dijkstra算法.ppt》由会员分享，可在线阅读，更多相关《图论动画-Dijkstra算法.ppt（13页珍藏版）》请在三一办公上搜索。
1、15.082 和 6.855J,Dijkstra 算法,2,一个例子,1,2,3,4,5,6,2,4,2,1,3,4,2,3,2,初始化,0,选择有最小临时距离标号的结点.,3,更新步,2,3,4,5,6,2,4,2,1,3,4,2,3,2,2,4,0,1,4,选择最小临时标号,1,3,4,5,6,2,4,2,1,3,4,2,3,2,2,4,0,2,5,更新步,1,2,3,4,5,6,2,4,2,1,3,4,2,3,2,2,4,6,4,3,0,结点 3 的前驱现在是结点 2,6,选择最小临时标号,1,2,4,5,6,2,4,2,1,3,4,2,3,2,2,3,6,4,0,3,7,更新,1,2,
2、4,5,6,2,4,2,1,3,4,2,3,2,0,d(5)没有变化.,3,2,3,6,4,8,选择最小临时标号,1,2,4,6,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,9,更新,1,2,4,6,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,d(4)没有变化,6,10,选择最小临时标号,1,2,6,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,6,4,11,更新,1,2,6,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,6,4,d(6)没有改变,12,选择最小临时标号,1,2,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,6,4,6,没有要更新的了,13,结束算法,1,2,2,4,2,1,3,4,2,3,2,0,3,2,3,6,4,5,6,4,6,现在所有结点都保持不变了,前驱形成了树,从结点 1 到结点 6 的最短路径能通过回溯前驱得到,
