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

Click to edit Master title style,Click to edit Master text styles,Second Level,Third Level,Fourth Level,Fifth Level,*,*,15.082,和,6.855J,修改的标号校正算法,修改的标号校正算法,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,2,LIST:=1,例子,3,通用步骤,从,LIST,中取一结点,i,0,2,3,3,1,6,-2,3,2,-4,4,3,Update(i):,对每条弧有,d(j,)d(i)+,c,ij,的的用,d(i)+,c,ij,替换,d(j,),3,LIST:=1,LIST:=,6,LIST:=2,LIST:=2,3,3,LIST:=2,3,4,0,3,例子,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)+,c,ij,的的用,d(i)+,c,ij,替换,d(j,),4,例子,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)+,c,ij,的用,d(i)+,c,ij,替换,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,LIST:=4,5,4,LIST:=5,6,LIST:=5,6,从,LIST,中取一结点,i,Update(i):,对每条弧有,d(j,)d(i)+,c,ij,的的用,d(i)+,c,ij,替换,d(j,),6,例子,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)+,c,ij,的用,d(i)+,c,ij,替换,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,LIST:=6,6,LIST:=,2,LIST:=3,9,LIST:=3,7,从,LIST,中取一结点,i,Update(i):,对每条弧有,d(j,)d(i)+,c,ij,的用,d(i)+,c,ij,替换,d(j,),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,LIST:=,2,LIST:=3,9,LIST:=3,7,2,LIST:=7,从,LIST,中取一结点,i,Update(i):,对每条弧有,d(j,)d(i)+,c,ij,的用,d(i)+,c,ij,替换,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:=3,7,LIST:=7,9,LIST:=,从,LIST,中取一结点,i,Update(i):,对每条弧有,d(j,)d(i)+,c,ij,的用,d(i)+,c,ij,替换,d(j,),10,例子,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:=,这是前驱。,11,