数学建模任意两点间最短距离

《数学建模任意两点间最短距离》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、任意两点间最短距离-floyd算法matlab程序%Floyd'sAlgorithm 通过一个图的权值矩阵求出它的任意两点间的最短路径矩阵。%Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，%稠密图效果最佳，边权可正可负。%此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行

2、V

3、次Dijkstra算法。 %a为图的带权邻接矩阵 %从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新， %即由矩阵D(0)=A，按一个公式

4、，构造出矩阵D(1)； %又用同样地公式由D(1)构造出D(2)；……； %最后又用同样的公式由D(n-1)构造出矩阵D(n)。 %矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵， %同时还可引入一个后继节点矩阵path来记录两点间的最短路径。 %采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);matlab函数文件为：function [D,path]=floyd1(a)a(find(a==0))=inf;n=si

5、ze(a,1); %计算出a的规模的大小.D=a;path=zeros(n,n);%设置D和path的初值.fori=1:n  forj=1:n     ifD(i,j)~=inf         path(i,j)=j;     end  endend%做n次迭代，每次迭代均更新D(i,j)和path(i,j)fork=1:n  fori=1:n     forj=1:n         ifD(i,k)+D(k,j)

6、j);             path(i,j)=path(i,k);         end     end  endendfori=1:n  D(i,i)=0;  path(i,i)=i;end关于path的说明：path（i，j）表示从i到j的最短路径中紧接着i后面的一个结点举例如下：无向图由该图的带权邻接矩阵（边权矩阵）a为：>>a=[035inf8inf3025inf75204inf3inf540618infinf602inf73120]a=   0  3  5 Inf  8 Inf

7、   3  0  2  5 Inf  7   5  2  0  4 Inf  3  Inf  5  4  0  6  1   8 Inf Inf  6  0  2  Inf  7  3  1  2  0然后将上述代码写入一个floyd1.m文件，在命令窗口中输入：>>[D,path]=floyd1(a);>>DD=   0  3  5  8  8  8   3  0  2  5  7  5   5  2  0  4  5  3   8  5  4  0  3  1   8  7  5  3  0

8、  2   8  5  3  1  2  0>>pathpath=   1  2  3  2  5  3   1  2  3  4  3  3   1  2  3  4  6  6   2  2  3  4  6  6   1  6  6  6  5  6   3  3  3  4  5  6解释：比如我们看到D(1,5)=8表示v1到到v5的距离是8，再查看具体路径，path(1,5)=5，表示v1到v5最短路径中紧接着v1的下一个顶点就是v5，说明边（v1,v5)就是最短路；再如，D(1,6

9、)=8，path(1,6)=3，path(3,6)=6，说明v1到v6的最短距离是8，最短路为v1->v3->v6。从D(1,6)=8=5+3=D(1,3)+D(3,6)可以得到验证。