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

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

1、15.082 和 6.855J,标号校正算法,2,例子,3,初始化,d(1):=0;d(j):=对于 j 1,1,2,4,5,3,6,7,2,3,3,1,6,-2,3,2,-4,4,3,0,在下一张幻灯片中:在结点中的数字是d(j).违规弧(violating arc)用加重的线表示.,3,例子,3,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,0,2,3,3,1,6,-2,3,2,-4,4,3,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,3,4,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,通用步骤,弧(i,j)是违规的，如果 d

2、(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,5,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,6,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,7,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,4,通用步骤,

3、弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,8,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,4,6,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,9,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,4,6,2,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,10,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,4,6,2,9,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,11,例子,3,0,2,3,3,1,6,-2,3,2,-4,4,3,3,6,3,5,4,6,2,9,没有弧违规,距离标号是最优的,现在我们说明前驱弧.,通用步骤,弧(i,j)是违规的，如果 d(j)d(i)+cij.,选择违规弧(i,j)，用 d(i)+cij 替换 d(i).,