《图论动画-修改的标号校正算法.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 125436723316-232-443 0 在下一张幻灯片中：在结点中的数字是在下一张幻灯片中：在结点中的数字是d(j).LIST:=12LIST:=1 例子例子3通用步骤通用步骤从从LIST中取一中取一结点结点 i0 23316-232-443Update(i):对每条弧有对每条弧有d(j)d(i)+cij 的的的用的用 d(i)+cij 替换替换 d(j)3LIST:=1LIST:=6LIST:=2 LIST:=2,3 3
2、LIST:=2,3,4 03例子例子30 23316-232-4433LIST:=1LIST:=6LIST:=2 LIST:=2,3 3LIST:=2,3,4 3LIST:=3,4 45LIST:=3,4,5 从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的的的用的用 d(i)+cij 替换替换 d(j)4例子例子30 23316-232-44336345LIST:=3,4,5 3LIST:=4,5 从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的用的用 d(i)+cij 替换替换 d(
3、j)5例子例子30 23316-232-44336345LIST:=3,4,5 LIST:=4,5 4LIST:=5 6LIST:=5,6 从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的的的用的用 d(i)+cij 替换替换 d(j)6例子例子30 23316-232-44336345LIST:=3,4,5 LIST:=4,5 LIST:=5 6LIST:=5,6 5LIST:=6 从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的用的用 d(i)+cij 替换替换 d(j)7例子例子3
4、0 23316-232-44336345LIST:=3,4,5 LIST:=4,5 LIST:=5 6LIST:=5,6 LIST:=6 6LIST:=2LIST:=3 9LIST:=3,7 从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的用的用 d(i)+cij 替换替换 d(j)8例子例子30 23316-232-44336345LIST:=3,4,5 LIST:=4,5 LIST:=5 6LIST:=5,6 LIST:=6 LIST:=2LIST:=3 9LIST:=3,7 2LIST:=7 从从LIST中取一中取一结点结点 iUpd
5、ate(i):对每条弧有对每条弧有d(j)d(i)+cij的用的用 d(i)+cij 替换替换 d(j)9例子例子30 23316-232-44336345LIST:=3,4,5 LIST:=4,5 LIST:=5 6LIST:=5,6 LIST:=6 LIST:=2LIST:=3 9LIST:=3,7 LIST:=7 9LIST:=从从LIST中取一中取一结点结点 iUpdate(i):对每条弧有对每条弧有d(j)d(i)+cij的用的用 d(i)+cij 替换替换 d(j)10例子例子3LIST 空了。空了。距离标号是最优的。距离标号是最优的。0 23316-232-44336345LIST:=3,4,5 LIST:=4,5 LIST:=5 6LIST:=5,6 LIST:=6 LIST:=2LIST:=3 9LIST:=3,7 LIST:=7 LIST:=这是前驱。这是前驱。11