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

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

1、15.082和6.855J修改的标号校正算法修改的标号校正算法3初始化d(1):=0;d(j):=对于j1125436723316-232-4430在下一张幻灯片中：在结点中的数字是d(j).LIST:={1}2LIST:={1}例子3通用步骤从LIST中取一结点i023316-232-443Update(i):对每条弧有d(j)>d(i)+cij的的用d(i)+cij替换d(j)3LIST:={1}LIST:={}6LIST:={2}LIST:={2,3}3LIST:={2,3,4}03例子3023316-232-4433

2、LIST:={1}LIST:={}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(j)5例子3023316-232-44336345LIST:={3,4,5}

3、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例子3023316-232-44336345LIST:={3,4,5}LIST:={4,5}LIST:

4、={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中取一结点iUpdate(i):对每条弧有d(j)>d(i)+cij的用d(i)+cij替换d(

5、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

6、}LIST:={}2LIST:={3}9LIST:={3,7}LIST:={7}LIST:={}这是前驱。11