《图论动画-标号校正算法.ppt》由会员分享，可在线阅读，更多相关《图论动画-标号校正算法.ppt（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、15.082 和和 6.855J 标号校正算法标号校正算法例子例子3初始化初始化 d(1):=0;d(j):=对于对于 j 1 124536723316-232-443 0 在下一张幻灯片中在下一张幻灯片中:在结点中的数字是在结点中的数字是d(j).违规弧违规弧(violating arc)用加重的线表示用加重的线表示.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,
2、j)是违规的，是违规的，如果如果 d(j)d(i)+cij.选择违规弧选择违规弧(i,j)，用，用 d(i)+cij 替换替换 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-
3、44336354通用步骤通用步骤弧弧(i,j)是违规的，是违规的，如果如果 d(j)d(i)+cij.选择违规弧选择违规弧(i,j)，用，用 d(i)+cij 替换替换 d(i).7例子例子30 23316-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-44336354629没有弧违规没有弧违规距离标号是最优的距离标号是最优的现在我们说明前驱弧现在我们说明前驱弧.通用步骤通用步骤弧弧(i,j)是违规的，是违规的，如果如果 d(j)d(i)+cij.选择违规弧选择违规弧(i,j)，用，用 d(i)+cij 替换替换 d(i).11