floyd算法C++实现.docVIP

#include #include using namespace std;#define MAXV 100#define INF 32767typedef int InfoType;typedef int Vertex;typedef struct int no; InfoType info; VertexType; /顶点类型typedef struct int edgesMAXVMAXV; int n,e; VertexType vexsMAXV; MGraph; /图类型void Ppath(int pathMAXV, int i, int j) int k; k=pathij; if (k=-1) return; /递归出口 Ppath(path,i,k); coutk ; /输出k Ppath(path,k,j); void Dispath(int AMAXV,int pathMAXV,int n) int i,j; for (i=0;in;i+) for (j=0;jn;j+) if (Aij=INF) if(i!=j) cout 从 i 到 j 不存在路径n; else cout 从 i 到 j 的路径为: i ; Ppath(path, i, j); coutj; cout tt 路径长度为:Aij endl; void Floyd(MGraph g) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for (i=0;ig.n;i+) for (j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for (k=0;kg.n;k+) for (i=0;ig.n;i+) for (j=0;j(Aik+Akj) Aij=Aik+Akj; pathij=k; Dispath(A,path,g.n); /输出最短路径 void DispMat(MGraph g)int i,j;for(i=0;ig.n;i+) for(j=0;jg.n;j+) if(g.edgesij=INF) cout setw(3) ; else coutsetw(3)g.edgesij; coutendl;void Floyd(MGraph g);void Ppath(int pathMAXV, int i, int j) ;void Dispath(int AMAXV,int pathMAXV,int n);void DispMat(MGraph g);void main()int i,j; MGraph g;coutg.ng.e;cout输入邻接矩阵g的元素值：n;for(i=0;ig.n;i+) cout第i行：; for(j=0;jg.edgesij;cout输出邻接矩阵g：n;DispMat(g);cout输出每对顶点之间的最短路径：n;Floyd(g);coutendl;C+语言：#include #define Maxm 501 using namespace std; ifstream fin; ofstream fout(APSP.out); int p,q,k,m; int Vertex,LineMaxm; int PathMaxmMaxm,DistMaxmMaxm; void Root(int p,int q) if (Pathpq0) Root(p,Pathpq); Root(Pathpq,q); else Linek=q; k+; int main() memset(Path,0,sizeof(Path); memset(Dist,0,sizeof(Dist); fin Vertex; for(p=1;p=Vertex;p+) for(q=1;q Distpq; for(k=1;k=Vertex;k+) for(p=1;p0) for(q=1;q0) if (DistpqDistpk+Distkq)|(Distpq=0)&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; for(p=1;p=Vertex;p+) for(q=p+1;q=Vertex;q+) fout n=n; fout Source: p n Target q n; fout Distance: Distpq n; fout Path: p; k=2; Root(p,q); for(m=2;m=k-1;m+) fout Linem; fout n; fout 2 = = Source:1 Target 3 Distance:45 Path:1-2-3 = = Source:1 Target 4 Distance:30 Path:1-4 = = Source:1 Target 5 Distance:70 Path:1-2-3-5 = = Source:1 Target 6 Distance:80 Path:1-2-3-5-6 = = Source:1 Target 7 Distance:130 Path:1-2-3-5-6-7 = = Source:2 Target 3 Distance:25 Path:2-3 = = Source:2 Target 4 Distance:50 Path:2-1-4 = = Source:2 Target 5 Distance:50 Path:2-3-5 = = Source:2 Target 6 Distance:60 Path:2-3-5-6 = = Source:2 Target 7 Distance:110 Path:2-3-5-6-7 = = Source:3 Target 4 Distance:40 Path:3-4 = = Source:3 Target 5 Distance:25 Path:3-5 = = Source:3 Target 6 Distance:35 Path:3-5-6 = = Source:3 Target 7 Distance:85 Path:3-5-6-7 = = Source:4 Target 5 Distance:55 Path:4-5 = = Source:4 Target 6 Distance:65 Path:4-5-6 = = Source:4 Target 7 Distance:115 Path:4-5-6-7 = = Source:5 Target 6 Distance:10 Path:5-6 = = Source:5 Target 7 Distance:60 Path:5-6-7 = = Source:6 Target 7 Distance:50 Path:6-7 =Matlab源代码为 %floyd算法通用程序，输入a为赋权邻接矩阵 %输出为距离矩阵D,和最短路径矩阵path function D,path=floyd(a) n=size(a,1); D=a; path=zeros(n,n); for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end end end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end end end %配合floyd算法的后续程序,s为源点,t为宿点 %L为长度,R为路由 function L,R