图论动画-标号校正算法

《图论动画-标号校正算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、换d(i).4例子3023316-232-443363通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).5例子3023316-232-4433635通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).6例子3023316-232-44336354通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).7例子3023316-

3、232-443363546通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).8例子3023316-232-4433635462通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).9例子3023316-232-44336354629通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).10例子3023316-232-443363546

4、29没有弧违规距离标号是最优的现在我们说明前驱弧.通用步骤弧(i,j)是违规的，如果d(j)>d(i)+cij.选择违规弧(i,j)，用d(i)+cij替换d(i).11