数学建模比赛最短路floyd算法

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）中存储着一条路径uv。现在我们考察，试着把a加到u、v的路

2、径上能否，得到一条更短的路径，即如果ua+avDbc=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)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)

3、c(ca,3)(cc,0)D(0)Dca+Dab=3+4Dcb= ，所以如果从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)(cab,7)(cc,0)D(0)从上面的D（0）开始，对于每两个顶点u、v，在D（0）中存储着一条路径uv。现在我们考察，试着把b加到u、v的路径上能否，得到一条更短的路径，即如果ub+bvuv的话，能够找到一条更短的路径。abc116423ab

4、ca(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)本来路径上源点或终点就有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)Dab+Dbc=6Dca=3，所以如果从b绕，反而远

5、，那么这一项不变。abc116423abca(aa,0)(ab,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)(bc,2)c(ca,3)(cab,7)(cc,0)D(0)从上面的D（1）开始，对于每两个顶点u、v，在D（1）中存储着一条路径uv。现在我们考察，试着把c加到u、v的路径上能否，得到一条更短的路径，即如果uc+cvDab=4，所以如果从c绕，反而远，那么这一项不变。abc116423abca(aa,0)(ab,4)(abc,6)b(bb,0)(bc,2)

6、c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)abc116423abca(aa,0)(ab,4)(abc,6)b(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)Dbc+Dca=2+3Dba=6，所以如果从c绕，更近，那么应该更新。abc116423abca(aa,0)(ab,4)(abc,6)b(bca,5)

7、(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)abca(aa,0)(ab,4)(abc,6)b(ba,6)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(1)Dbc+Dca=2+3Dba=5，所以如果从c绕，更近，那么应该更新。现在，已经把所有的顶点都试了一遍，算法结束。每两个顶点之间的路径如D(2)所示。abca(aa,0)(ab,4)(abc,6)b(bca,5)(bb,0)(bc,2)c(ca,3)(cab,7)(cc,0)D(2)采用图的邻接矩阵的存储结构怎样构造一个图，在此不赘述，直接给出floyd-wallshall算法。void MD

8、Net:Floyd(CDC *pDC)typedef vector path;/使用顺序表模板path pmax_vertex_nummax_vertex_num;/p存放每对顶点之间的最短路径int Dmax_vertex_nummax_vertex_num;/ D存放每对顶点之间的最短路径值int i,j,k;for(i=1;i=vex_num;i+)/初始化for(j=1;j=vex_num;j+)pij.push_back(i);pij.push_back(j);/顶点i和顶点j之间的路径初始时就是ij。Dij=arcsij;/路径值为边（i，j）的权值 for(k=1;k=vex_num;k+) /对于每一个顶点都要试探for(i=1;i=vex_num;i+)for(j=1;j=vex_num;j+)/在顶点i和顶点j之间的路径上试探kif(i=j)continue;/对角线上的元素（即顶点自身之/间）不予考虑if(Dik+DkjDij)/发现更短的路径Dij=Dik+Dkj;/新的i、j间的路径由两部分组成/pik+pkjpij=pikfor(int m=1;mpkj.size();m+)