弗洛伊德算法求解最短路径

1、课程设计任务书课程设计名称数据结构课程设计专业计算机科学与技术（物联网方向）学生姓名班级学号题目名称最短路径求解起止日期2015 年 1 月 5日起至2015 年1月 16 日止课设内容和要求：内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间 存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任 意其他任意城市的最短路径冋题。要求：1）能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称， 城市编号等；2）利用矩阵保存城市间的距离；3）利用Floyd算法求最短路径；4）独立元成系统的设计，编码和调试；5）系统利用C语言完成；6）按照课

2、程设计规范书写课程设计报告。 参考资料：算法与数据结构C语言程序设计教研室审核意见：教研室主任签字：指导教师（签名）年月日学生（签名）年月日目 录第1章概要设计11.1题目的内容与要求112总体结构1第2章详细设计22.1主模块22.2构建城市无向图 32.3添加城市42.4修改城市距离52.5求最短路径6第3章调试分析73.1调试初期73.2调试中期73.3调试末期7第4章测试及运行结果7附页（程序清单）10第1章概要设计1.1题目的内容与要求内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城 市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出 发到达任意

3、其他任意城市的最短路径问题。要求：1）能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；2）利用矩阵保存城市间的距离；3）利用Floyd算法求最短路径；4）独立完成系统的设计，编码和调试；5）系统利用C语言完成；6）按照课程设计规范书写课程设计报告。1.2总体结构本程序主要分为四个模块（功能模块见图 1.1）:主模块对整个程序起一主导 作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据 进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。Floyd算法求最短建城市图添 加 城 市 顶 占 八、修 改 城 市 距 离求 最 短 路

4、径图1.1功能模块图第2章详细设计2.1主模块用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2 : 建立城市无向图2.3 :添加城市2.4 :修改城市距离2.5 :求最短路径。流程图中 通过输入n,由n的值来选择调用相对应子函数，实现所选择的功能，调用完后 可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块 的功能等。图2.1主模块流程图2.2构建城市无向图根据提示输入城市，对城市无向矩阵图进行初始化，开始g.

5、vm n.path的路径值赋为-2表示p城到q城间中间没有可达的路径不经过其他城市，而 g.vmn.distanee赋值为0表示p到p的距离为0。流程图中的MAX表示的 是最多的城市数量，其值为 20； p，q表示城市的编号，而 path和distanee 分别表示的路径和城市间距离。g.vpq.distaee表示p、q代表的城市间的距 离图2.2构建城市无向图流程图2.3添加城市用户根据提示输入想要添加到无向图中的城市，根据屏幕中的提示输入与之 邻接的城市间的距离，然后添加城市距离矩阵图中；同时将g.vmn.path赋值为 -1即表示p城到q城有路可达且最短路径无需经过其他城市。需注意的是当

6、 g.vmn.distance=O 表示 p 城到 q 城的距离为 0，当 g.vmn.distance=99999，则 表示p城到q城距离无穷大即表示他们之间无路径可达，而当 g.vmn.distance=k(0<k<99999)时表示他们间的距离是 k。流程图中g.n表示当前 图中存储的城市数量，dis表示输入的城市间的距离即q和g.n表示城市间的距离。 通过q<g.n的条件判断来充分完成图对应的矩阵中的赋值。图2.3添加城市流程图结束2.4修改城市距离根据屏幕上的城市编号，输入想更改的城市编号。在进行该模块时会输出原 来的距离。由于在现实生活中由于一些人为的测量误差或是

7、一些自然因素，又或 是城市整编等等一系列的因素需要改动原来的城市距离，此时应用该块修改的功 能即可实现更改，且根据提示操作简单，用户具体可以参看第四章：测试及运行结果。流程图中p,q表示城市的编号，根据p和q可以找到对应的城市名称，找 到对应的g.vpq.distanee即是原来两城市间的距离。图2.4修改城市距离流程图2.5求最短路径利用Floyd求最短路径，假设vi到vj存在路径，长度为k，假设vi到vj经过vk(i=0 1.n)长度为m,比较k和m,如果k>m,则d(vi,vj)=m,否则为k，依次类推，直到所有的vi到vj的中间城市比较完，最后d(vi,vj)的值即为最短距离，同

8、时在 比较的过程中保存路径信息，最后在查询时即可输出路径。具体见 第四章：测试 及运行结果中求最短路径界面图2.4修改城市距离流程图开始i=j=k=0g.vij.dista nce=g.vik.dista n ce+g.vkj.dista nee path=k j+ k+ i+I .第3章调试分析3.1调试初期由于编写的程序具有模块化的特性，且 VC 6.0的调试显然由于TC及个 人对VC的熟练程度远优于TC等方面，我选择先在VC6.0环境下完成除图形化演 示算法过程函数的其他过程。由于数据结构选择的较合理，对 Floyd算法的理解较为深刻，所以在此环境 下的调试并没有太多困难。3.2调试中期

9、在上机输入完程序后，出现了许多错误，其中有一些小错误，比如说忘记写 分号，在这些错误上双击，找到位置，加上分号。还有就是程序中的有的变量在 前面没有定义，只要在前面添加上就可以了。再有就是前后的类型要保持一致，在这块我也犯了个错误。前面是指针类型, 后面却是取地址类型，解决办法就是把前面的改成指针类型，保持前后一致。 还有就是遗忘分号，逗号，解决方法就是， 一步一步的把遗忘的分号，逗号补上。忘记定义变量的类型。比i应该是整型的却忘记申明。解决方法就是在函数 内先申明int类型的i.。粗心导致很多细节问题，比如该输入英文的括号的，却 输成中文的括号，解决方法，把中英文分开。注意细节问题。3.3调

10、试末期输入的数据无法找出正确的路径，解决方法，一步一步的调试，找出问题的 所在，改正逻辑错误。在同学的帮助下，找到了逻辑错误，一步一步地改正，终 于得到预期的结果。第4章测试及运行结果建图过程：根据屏幕上的显示输入，你会看到如下界面；"H:EE 径Debug眉径番 比的市 1迁 MB 创添加城市过程：根据界面提示操作，结果如下，添加一城市后如下:1234退岀程序鹽人添加城市的名字 爲和h城杲否邻接是的 1不杲！ B请输人裁和b城间於距离106是否抵续1=绝续0=退出面 界 下 如 果 结 后 最了 加 添 共 总 我的、巾操图靄隹序 - - 召三 ! 12 3 4-5靜入添加城帛的名

11、字&铁和止城是否邻接是的* 1不是.R:青输入谢和1城间常跖离35Eb城和出城是否邻接是的】1不是I 0溝轲入b城和1城间笊距离4盹c城和cl城杲否邻接是的* 1不杲：0淪入c城和城间的距离370微软折咅简捷半=求最短路径过程：根据提示我输入了 0 2号城市编号，结果如下作的巾操1 一理4J - - » » » 12 3 4-5S1 绩 25否 离 石wb 最绎 MM 禾至出_艮同理根据提示输入要修改的城市编号，输入后，屏幕上会显示原来的距离，输入 修改后的距离即可修改成功。附页(程序清单)#i nclude "stdafx.h"#in

12、 clude<stdio.h>#in clude<stri ng.h>#in clude<stdlib.h>#i nclude <malloc.h>#define MAX 20 / 城市数量typedef structint path;int dista nee; Vert;typedef structint n;存放顶点数char nameMAX60;城市名称及编号Vert vMAXMAX; Mgraph;void path(Mgraph g,i nt m,i nt n ,i nt f)int k,i,a21;for(i=0;i<21;i

13、+)ai=-3;k=g.vm n.path;if(k>=0)f+;af=k;k=g.vmk.path;path(g,m,k,f);k=g.vk n .path;path(g,k, n,f);for(i=1;ai>=0;i+)printf("%s 到%s 途经:",m,n);printf("%s",ai);void Floyd(Mgraph g)int i,j,k,m,n,h=0,w=0,f=0,s;for(k=0;k<g. n-1;k+)for(i=0;i<g. n-1;i+)for(j=0;j

14、<g. n;j+)if(g.vij.dista nce>g.vik.dista nce+g.vkj.dista nee)g.vij.dista nce=g.vik.dista nce+g.vkj.dista nee;g.vji.dista nce=g.vij.dista nee;g.vij.path=k;g.vji.path=g.vij.path;printf("输入你要查询的两城市编号n");printf("以下是城市相对应的编号:n");for(i=0;i<g. n;i+)w+;prin tf("%s: %d",

15、g. namei,i);if(w%g. n=0)prin tf("n");scan f("%d%d",&m,&n);printf("%s 和 %s 的最短距离是 %dn",m,n,g.vmn.distanee); s=g.vm n.path;if(s=-1)printf("%s 到%s 最短路径不途经其他城市n”,m,n);if(s>=0)path(g,m, n,f);Mgraph Modify(Mgraph g) / 修改俩城市的数据int p,q,s;

16、printf("输入要修改的两城市编号n",g.vpq.distanee);sca nf("%d%d", &p, &q);printf("原来两城市距离为%dn");printf("修改两城市间的距离n");sca nf("%d", &s);g.vpq.dista nce=s;return g;Mgraph ADD(Mgraph g) / 添加新的城市int p=O,q=O,dis;char s;printf("请输入添加城市的名字 n");scan

17、f("%s", &g. nameg. n);for(q=0;q<g .n; q+)printf("%s 和 %s 是否邻接 是的：1 不是：On",q,g.n); sca nf("%d",&p);if(p=1)/邻接信息g.vqg. n.path=-1;printf("请输入 %s 和 %s 间的距离 n",q,g.n);scan f("%d", &dis);g.vqg. n.dista nce=dis;g.vg .n

18、 q.dista nce=dis;elseg.vqg.n.distance=99999;/99999 表示距离的无限大值g.vg.nq.distance=99999;/99999 表示距离的无限大值g.n+;return g;/添加结束Mgraph Init(Mgraph g)/初始化一个邻接矩阵无向图int q=0,p=0;g.n=1;printf("请输入第一个城市的名称n");scan f("%s",g. nameO);for(q=0;q<MAX;q+)for(p=0;p<MAX;p+)g.vpq.path=-2;g.vqq.dista

19、 nce=O ;return g;/初始化结束void main()int i,m=0; Mgraph p; doprin tf("|n");prin tf("|选择操作|n")prin tf("|1.创建一个图|n");prin tf("|2.添加一个新的城市|n");prin tf("|3.修改现有城市的数据|n");prin tf("|4.求取短路径|n");prin tf("|5退出程序|n");prin tf("|n");sca nf("%d",&i);switch(i)case 1:p=Init(p);brea