图论动画-修改的标号校正算法.ppt

《图论动画-修改的标号校正算法.ppt》由会员分享，可在线阅读，更多相关《图论动画-修改的标号校正算法.ppt（11页珍藏版）》请在三一办公上搜索。

1、15.082 和 6.855J,修改的标号校正算法,2,修改的标号校正算法,3,初始化,d(1):=0;d(j):=对于 j 1,1,2,5,4,3,6,7,2,3,3,1,6,-2,3,2,-4,4,3,0,在下一张幻灯片中：在结点中的数字是d(j).,LIST:=1,3,LIST:=1,例子,3,通用步骤,从LIST中取一结点 i,0,2,3,3,1,6,-2,3,2,-4,4,3,Update(i):对每条弧有d(j)d(i)+cij 的的用 d(i)+cij 替换 d(j),3,LIST:=1,LIST:=,6,LIST:=2,LIST:=2,3,3,LIST:=2,3,4,0,4,例

2、子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,LIST:=1,LIST:=,6,LIST:=2,LIST:=2,3,3,LIST:=2,3,4,3,LIST:=3,4,4,5,LIST:=3,4,5,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的的用 d(i)+cij 替换 d(j),5,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,3,LIST:=4,5,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的用 d(i)+cij 替换 d(j),6,例

3、子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,4,LIST:=5,6,LIST:=5,6,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的的用 d(i)+cij 替换 d(j),7,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,LIST:=5,6,LIST:=5,6,5,LIST:=6,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的用 d(i)+cij 替换 d(j),

4、8,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,LIST:=5,6,LIST:=5,6,LIST:=6,6,LIST:=,2,LIST:=3,9,LIST:=3,7,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的用 d(i)+cij 替换 d(j),9,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,LIST:=5,6,LIST:=5,6,LIST:=6,LIST:=,2,LIST:=3,9,LIST

5、:=3,7,2,LIST:=7,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的用 d(i)+cij 替换 d(j),10,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,LIST:=5,6,LIST:=5,6,LIST:=6,LIST:=,2,LIST:=3,9,LIST:=3,7,LIST:=7,9,LIST:=,从LIST中取一结点 i,Update(i):对每条弧有d(j)d(i)+cij的用 d(i)+cij 替换 d(j),11,例子,3,LIST 空了。距离标号是最优的。,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,4,5,LIST:=3,4,5,LIST:=4,5,LIST:=5,6,LIST:=5,6,LIST:=6,LIST:=,2,LIST:=3,9,LIST:=3,7,LIST:=7,LIST:=,这是前驱。,