floyd弗洛伊德算法.ppt

《floyd弗洛伊德算法.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、)(bc,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)abc1

4、16423abca(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、11)b(ba,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、0)本来路径上源点或终点就有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、bca(aa,0)(ab,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,

8、4)(abc,6)b(ba,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)(