762每一对顶点间的最短路径.ppt

《762每一对顶点间的最短路径.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、7.6.2每一对顶点间的最短路径Dijkstra算法是求源点到其它顶点的最短路径。怎样求任意两个顶点之间的最短路径？我们可以把Dijkstra算执行n次，每次从不同的顶点开始，则算法时间复杂度为O（n3）。Floyd弗洛伊德给出了另一个算法，时间复杂度也是O（n3），但是形式上简单些。从演示中看算法思想一个简单的图及其邻接矩阵如下：abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)从上面的D（-1）开始，对于每两个顶点u、v，在D（-1）中存储着

2、一条路径u…v。现在我们考察，试着把a加到u、v的路径上能否，得到一条更短的路径，即如果u…a+a…v

3、,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)c(ca,3)(cc,0)D(0)D[b][a]+D[a][c]=6+11>D[b][c]=2，所以如果从a绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)abc116423a

4、bca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cb,∞)(cc,0)D(-1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cc,0)D(0)D[c][a]+D[a][b]=3+4

5、6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)从上面的D（0）开始，对于每两个顶点u、v，在D（0）中存储着一条路径u…v。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果u…b+b…v

6、终点就有b的不必考虑。对角线上的也不必考虑abc116423abca(aa,0)(ab,4)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)D[a][b]+D[b][c]=6

7、,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)abc116423abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)D[c][b]+D[b][a]=7+6>D[c][a]=3，所以如果从b绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(abc,6)b(ba,

8、6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)abca(aa,0)(ab,4)(ac,11)b(ba,6)(bb,0)(