最短最优路径算法附程序代码

《最短最优路径算法附程序代码》由会员分享，可在线阅读，更多相关《最短最优路径算法附程序代码（11页珍藏版）》请在装配图网上搜索。

1、实验报告一题目要求输入N(NvlO)个城市，每两个城市之间有对应的距离和费用(可以不能到达)，要 求实现如下程序：a) 给出任意两个城市之间的最短距离，及其到达方式；b) 给出任意两个城市之间的最小费用，及其到达方式；c) 权衡距离和费用，给出任意两个城市之间的最优路径，及其到达方式；PS：l. 距离矩阵和费用矩阵由同学自己给出；2. 题c)的最优路径由自己定义。二算法设计：欲求得每一对顶点之间的最短路径，解决这一问题的办法是采用弗洛伊德算法。弗洛伊德算法仍从图的带权邻接矩阵出发，其主要思想是：设集合S的初始状态 为空集合，然后依次向集合S中加入顶点V0,V1,V2,，Vn-1，每次加入一个顶

2、点， 我们用二维数组D保存每一对顶点之间的最短路径的长度，其中，Dij存放从顶点 Vi到Vj的最短路径的长度。在算法执行中，Dij被定义为：从Vi到Vj的中间只经 过S中的顶点的所有可能的路径中最短路径的长度(如果从Vi到Vj中间只经过S中的 顶点当前没有路径相通，那么dij为一个大值MaxNum)。即dij中保存的是从Vi 到Vj的“当前最短路径”的长度。每次加入一个新的顶点，Vi和Vj之间可能有新的 路径产生，将它和已经得到的从Vi到Vj的最短路径相比较，dij的值可能需要不断 修正，当S=V时，dij的值就是从Vi到Vj的最短路径。因为初始状态下集合S为空集合，所以初始化Dij=Aij

3、(Aij是图的邻接矩 阵)的值是从Vi直接邻接到Vj,中间不经过任何顶点的最短路径。当S中增加了顶点 V0,那么D(0)ij的值应该是从Vi到Vj,中间只允许经过v0的当前最短路径的长度。 为了做到这一点，只需对D(0)ij 作如下修改：D(0)ij=minDij,Di0+D0j一般情况下，如果D(k-1)ij是从Vi到Vj,中间只允许经过 V0,V1,V2,， Vk-1的当前最短路径的长度，那么，当S中加进了 Vk,则应该对D进行修改如下：D(k)ij=minD(k-1)ij,D(k-1)ik+D(k-1)kj 三概要设计：1. 数据结构 二维数组来表示邻接矩阵，数组中存储元素表示邻接点之间

4、的距离，或费用。2. 抽象数据类型有向图3. 函数接口Void main() 主函数Void Dispmat() 输出邻接矩阵函数Void Floyed() 计算最短路径函数 Void Dispath() 输出最短路径函数 四详细设记Main 函数的流程图如下：DispMat(MGraph g) 函数流程图如下：Dispath(double AMAXV,int pathMAXV,int n)函数流程图如下:NYNJ+i!=jY罟Yij= Typrintf (从 4到4的 路径为:,i,j);printf(%d,i); ppath(path,i,j); printf(%d,j);printf(路

5、径长度为:.2lfn, (double)Aij);printf(从 %d 到%d没有路径开始i=O,j=O结束Floyd（MGraph g）函数流程图如下:K=O,i=O,j=Oj+kvnYini +NjAik+Yprintf（n输出最短 路径:n）; Dispath（A,path,n）;输出最短路径Aij=Aik+ Akj; pathij=k;k +j +结束五调试分析与心得体会 本次程序开始之初，我首先构思了大致结构，考虑到需要多个函数来完成功能，我 从各个子函数开始，编写各个子函数。本次设计的重点是FLOYD算法。计算最优路径 的核心思想是FLOYD算法。我花费了大量的时间编写FLOYD

6、函数，并进行多次修改 才可以正常运行。从最初程序的短短几十行到本次程序的一百多行，此次设计让我收获 颇多。函数编写过程中遇到多处错误，经过思考和与同学探讨最终正确完成了程序。六用户操作说明及运行结果显示 首先请输入城市个数和弧数（整型数据）: 5 10。1. 下面计算任意两个城市之间的最短距离: 请输入距离矩阵的边（以-1 -1 -1作为结束标志）:每组数据输入两个邻接点和其间距 离，数据间以空格隔开。Eg. 1 3 50 4 122 1 8-1 -1 -1D: 0Debug0. exe10.下面计算任意两个城市之间的最短距离：请输入距离矩阵的边（以“-1 -1 -1“作为结束标志:3 54

7、121 81 -1 -1CO CO CO 12.00CO .00 500 CO8.00 CO co co5.00 co co co .00 CO CO CO CO路径长度为= 24.00路径长度为= 12-000 0 00 0 _M 18 5 度度度 -K-K-K 路路路0 0 0 0 - _b 0J 8 11 度度度 -K-K-K 路路路0 00 0 0 0 - -3 0 5 11 知知知 度度度 -K-K-K 路路路路径长度为：12.000a4a0-知为径为为为iWi为为为为为为径为为 鲁路路路径路ItWl路路ItWl路路路径路路路径 蹈蹈有有有路有路蹈蹈有有路蹈蹈有有路路路有路有有有路

8、趣的沁KK扁蔦的的沁K扁的的沁K侖的的番沁KK爲 聂 0 123401234012340123401234 出一？1a3 2 3 p p P 1112 3 111 p p P 2 2 22 31113 3 3到到到到到到到到到到到到到到到到到到到到到到到到到00000111112222233333444442. 下面计算任意两个城市之间的最小费用：请输入费用矩阵的边（以-1 -1 -1作为结束标志）: 每组数据输入两个邻接点和其间费 用，数据间以空格隔开。Eg. 2 3 70 4 21 3 6-1 -1 -10 0 0 0 00- -2 6 7 1 度度度 * 路路路0 0 0 -0 2 3

9、- 116 度度度 *0 & b00 & aO+bO=l a0和 b0 都为小数）：Eg. 0.25 0.75g *D:0Debug0. eze*请输入权值,b00 .25 0.75J-卫卄：1 I W | J二_ |.1 H .耳：口 |丄,T=.l& b00 & a0+b0=l 龍和丽都为小数：COD CO CO CO 4.50j co 245775_75 co:=：1 24577.2石 co 8197.00:=：1 5.75 8197.00 co co.50 co co co co路径长度为：9.师路径长度为：4.50路逢长度为：11-S0難iB：證誉111度度度 -K-K-K 路路路5

10、 7 5 7 9 4 4 5 8 1 度度度 -K-K-K 路路路12 1路径长度为:为为径为为为iWi为为为iWi为为为径为为赛路路路径路路路W路路W路径路路路径 路路有有有路有路路路有有路路路有有路路路有路有有有路 短的沁KK爲瞻的的沁保舄的的沁K爲的的篇沁KK侖 dl至至爭至至至至至至至至至至至至至至至至至至至至至至 Hn00000111112222233333444440123401234012340123401234请输入权值aB,b00& b00 & aB+b0=l 嗣和h0者鸟为小数：八附件 附有源程序如下： #include #define INF 32767 typedef

11、int InfoType;#define MAXV 100/最大顶点个数/以下定义邻接矩阵类型typedef struct int no;/顶点编号InfoType info;/顶点其他信息，这里用于存放边的权值VertexType;/顶点类型typedef struct/图的定义double edgesMAXVMAXV; /邻接矩阵 int n,e;/顶点数，弧数VertexType vexsMAXV; /存放顶点信息MGraph;/图的邻接矩阵类型void DispMat(MGraph g)输出邻接矩阵Gint i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(

12、g.edgesij=INF)printf(%3s,Q);elseprintf(%.2lf,g.edgesij);printf(n);void ppath(int pathMAXV,int i,int j)int k;k=pathij;if(k=-1)return;ppath(path,i,k);printf(%d,k);ppath(path,k,j);void Dispath(double AMAXV,int pathMAXV,int n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)if(Aij=INF) if(i!=j)printf(从d到小没有路径n,i,j);

13、elseprintf(从4 到d 的路径为:,i,j); printf(%d,i);ppath(path,i,j);printf(%d,j);printf(t 路径长度为:.2lfn,(double)Aij);/采用弗洛伊德算法求每对顶点之间的最短路径void Floyd(MGraph g)double AMAXVMAXV;int pathMAXVMAXV;int i,j,k,n=g.n;for(i=0;in;i+)for(j=0;jn;j+)Aij=g.edgesij; pathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jAik+Akj)Aij=Ai

14、k+Akj; pathij=k;printf(n输出最短路径:n);Dispath(A,path,n); /输出最短路径void main()int i,j,u=0,m,k,num;MGraph g;int AMAXVMAXV,BMAXVMAXV;double CMAXVMAXV,a0,b0; for(k=0;kMAXV;k+)for(m=0;mMAXV;m+)Akm=INF;for(k=0;kMAXV;k+) for(m=0;mMAXV;m+)Bkm=INF;for(k=0;kMAXV;k+) for(m=0;mMAXV;m+)Ckm=INF;printf(请输入城市个数和弧数：n);sca

15、nf(%d %d,&g.n,&g.e);printf(l.下面计算任意两个城市之间的最短距离：n);printf(”请输入距离矩阵的边(以-1 -1 -1作为结束标志):n); while(l)scanf(%d,&i); scanf(%d,&j);scanf(%d,&num); if(i=-1 & j=-1 & num=-1) break; if(i=g.n) | (j=g.n)printf(输入错误!)； Aij=Aji=num;for(i=0;ig.n;i+) for(j=0;jg.n;j+) g.edgesij=Aij;printf(n);printf(有向图G的邻接矩阵:n); Dis

16、pMat(g);Floyd(g);printf(n);printf(2.下面计算任意两个城市之间的最小费用：n);printf(请输入费用矩阵的边(以-1 -1 -1作为结束标志):n); while(1)scanf(%d,&i); scanf(%d,&j);scanf(%d,&num); if(i=-1 & j=-1 & num=-1) break; if(i=g.n) | (j=g.n)printf(输入错误!)； Bij=Bji=num;for(i=0;ig.n;i+) for(j=0;jO & b00 & aO+bO=l a0 和 b0 都为小数):n); scanf(%lf,&a0); scanf(%lf,&b0);if(a0=-l & b0=-l) break; for(k=0;kg.n;k+) for(m=0;mg.n;m+) if(Akm=INF & Bkm=INF) Ckm=INF; else Ckm=(double)Akm*a0+(double)Bkm*b0;for(i=0;ig.n;i+) for(j=0;jg.n;j+)g.edgesij=Cij;printf(n);printf(有向图G的邻接矩阵:n);DispMat(g);Floyd(g);printf(n);