弗洛伊德算法求解最短路径.docx
《弗洛伊德算法求解最短路径.docx》由会员分享，可在线阅读，更多相关《弗洛伊德算法求解最短路径.docx（20页珍藏版）》请在冰点文库上搜索。
弗洛伊德算法求解最短路径
课程设计任务书
课程设计名称
数据结构课程设计
专业
计算机科学与技术
（物联网方向）
学生姓名
班级
学号
题目名称
最短路径求解
起止日期
2015
年
1
月
5
日起至
2015
年
1
月
16
日止
课设内容和要求：
内容：
给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。
试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。
要求：
1）能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；
2）利用矩阵保存城市间的距离；
3）利用Floyd算法求最短路径；
4）独立完成系统的设计，编码和调试；
5）系统利用C语言完成；
6）按照课程设计规范书写课程设计报告。
参考资料：
《算法与数据结构》
《C语言程序设计》
教研室审核意见：
教研室主任签字：
指导教师（签名）
年
月
日
学生（签名）
年
月
日
第1章概要设计
1.1题目的内容与要求
内容：
给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。
试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。
要求：
1）能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名称，城市编号等；
2）利用矩阵保存城市间的距离；
3）利用Floyd算法求最短路径；
4）独立完成系统的设计，编码和调试；
5）系统利用C语言完成；
6）按照课程设计规范书写课程设计报告。
1.2总体结构
本程序主要分为四个模块（功能模块见图1.1）：
主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。
添加城市
顶点
图1.1功能模块图
第2章详细设计
2.1主模块
用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。
程序的总框架大致分为四个模块：
1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。
具体实现过程见2.2：
建立城市无向图2.3：
添加城市2.4：
修改城市距离2.5：
求最短路径。
流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。
图2.1主模块流程图
2.2构建城市无向图
根据提示输入城市，对城市无向矩阵图进行初始化，开始g.v[m][n].path的路径值赋为-2表示p城到q城间中间没有可达的路径不经过其他城市，而g.v[m][n].distance赋值为0表示p到p的距离为0。
流程图中的MAX表示的是最多的城市数量，其值为20；p，q表示城市的编号，而path和distance分别表示的路径和城市间距离。
g.v[p][q].distace表示p、q代表的城市间的距离
图2.2构建城市无向图流程图
否
是
否
是
2.3添加城市
用户根据提示输入想要添加到无向图中的城市，根据屏幕中的提示输入与之邻接的城市间的距离，然后添加城市距离矩阵图中；同时将g.v[m][n].path赋值为-1即表示p城到q城有路可达且最短路径无需经过其他城市。
需注意的是当g.v[m][n].distance=0表示p城到q城的距离为0，当g.v[m][n].distance=99999，则表示p城到q城距离无穷大即表示他们之间无路径可达，而当g.v[m][n].distance=k（0流程图中g.n表示当前图中存储的城市数量，dis表示输入的城市间的距离即q和g.n表示城市间的距离。
通过q图2.3添加城市流程图
否
是
否
是
是
2.4修改城市距离
根据屏幕上的城市编号，输入想更改的城市编号。
在进行该模块时会输出原来的距离。
由于在现实生活中由于一些人为的测量误差或是一些自然因素，又或是城市整编等等一系列的因素需要改动原来的城市距离，此时应用该块修改的功能即可实现更改，且根据提示操作简单，用户具体可以参看第四章：
测试及运行结果。
流程图中p,q表示城市的编号，根据p和q可以找到对应的城市名称，找到对应的g.v[p][q].distance即是原来两城市间的距离。
图2.4修改城市距离流程图
2.5求最短路径
利用Floyd求最短路径，假设vi到vj存在路径，长度为k，假设vi到vj经过vk（i=01…..n）长度为m,比较k和m,如果k>m,则d（vi,vj）=m,否则为k，依次类推，直到所有的vi到vj的中间城市比较完，最后d（vi,vj）的值即为最短距离，同时在比较的过程中保存路径信息，最后在查询时即可输出路径。
具体见第四章：
测试及运行结果中求最短路径界面
图2.4修改城市距离流程图
否
是
否
是
否是
是
是
第3章调试分析
3.1调试初期
由于编写的程序具有模块化的特性，且VC6.0的调试显然由于TC及个人对VC的熟练程度远优于TC等方面，我选择先在VC6.0环境下完成除图形化演示算法过程函数的其他过程。
由于数据结构选择的较合理，对Floyd算法的理解较为深刻，所以在此环境下的调试并没有太多困难。
3.2调试中期
在上机输入完程序后，出现了许多错误，其中有一些小错误，比如说忘记写分号，在这些错误上双击，找到位置，加上分号。
还有就是程序中的有的变量在前面没有定义，只要在前面添加上就可以了。
再有就是前后的类型要保持一致，在这块我也犯了个错误。
前面是指针类型，后面却是取地址类型，解决办法就是把前面的改成指针类型，保持前后一致。
还有就是遗忘分号，逗号，解决方法就是，一步一步的把遗忘的分号，逗号补上。
忘记定义变量的类型。
比i应该是整型的却忘记申明。
解决方法就是在函数内先申明int类型的i.。
粗心导致很多细节问题，比如该输入英文的括号的，却输成中文的括号，解决方法，把中英文分开。
注意细节问题。
3.3调试末期
输入的数据无法找出正确的路径，解决方法，一步一步的调试，找出问题的所在，改正逻辑错误。
在同学的帮助下，找到了逻辑错误，一步一步地改正，终于得到预期的结果。
第4章测试及运行结果
建图过程：
根据屏幕上的显示输入，你会看到如下界面；
添加城市过程：
根据界面提示操作，结果如下，添加一城市后如下：
我总共添加了三个城市，最后结果如下界面：
求最短路径过程：
根据提示我输入了02号城市编号，结果如下：
同理根据提示输入要修改的城市编号，输入后，屏幕上会显示原来的距离，输入修改后的距离即可修改成功。
附页（程序清单）
#include"stdafx.h"
#include
#include
#include
#include
#defineMAX20//城市数量
typedefstruct{
intpath;
intdistance;
}Vert;
typedefstruct{
intn;//存放顶点数
charname[MAX][60];//城市名称及编号
Vertv[MAX][MAX];
}Mgraph;
voidpath（Mgraphg,intm,intn,intf）
{
intk,i,a[21];
for（i=0;i<21;i++）
a[i]=-3;
k=g.v[m][n].path;
if（k>=0）
{
f++;
a[f]=k;
k=g.v[m][k].path;
path（g,m,k,f）;
k=g.v[k][n].path;
path（g,k,n,f）;
}
for（i=1;a[i]>=0;i++）
{
printf（"%s到%s途经:
",g.name[m],g.name[n]）;
printf（"%s",g.name[a[i]]）;
}
}
voidFloyd（Mgraphg）
{
inti,j,k,m,n,h=0,w=0,f=0,s;
for（k=0;k{
for（i=0;ifor（j=0;j{
if（g.v[i][j].distance>g.v[i][k].distance+g.v[k][j].distance）
{
g.v[i][j].distance=g.v[i][k].distance+g.v[k][j].distance;
g.v[j][i].distance=g.v[i][j].distance;
g.v[i][j].path=k;
g.v[j][i].path=g.v[i][j].path;
}
}
}
printf（"输入你要查询的两城市编号\n"）;
printf（"以下是城市相对应的编号:
\n"）;
for（i=0;i{
w++;
printf（"%s:
%d",g.name[i],i）;
if（w%g.n==0）
printf（"\n"）;
}
scanf（"%d%d",&m,&n）;
printf（"%s和%s的最短距离是%d\n",g.name[m],g.name[n],g.v[m][n].distance）;
s=g.v[m][n].path;
if（s==-1）
printf（"%s到%s最短路径不途经其他城市\n",g.name[m],g.name[n]）;
if（s>=0）
path（g,m,n,f）;
}
MgraphModify（Mgraphg）//修改俩城市的数据
{
intp,q,s;
printf（"输入要修改的两城市编号\n",g.v[p][q].distance）;
scanf（"%d%d",&p,&q）;
printf（"原来两城市距离为%d\n"）;
printf（"修改两城市间的距离\n"）;
scanf（"%d",&s）;
g.v[p][q].distance=s;
returng;
}
MgraphADD（Mgraphg）//添加新的城市
{
intp=0,q=0,dis;
chars;
printf（"请输入添加城市的名字\n"）;
scanf（"%s",&g.name[g.n]）;
for（q=0;q{
printf（"%s和%s是否邻接是的：
1不是：
0\n",g.name[q],g.name[g.n]）;
scanf（"%d",&p）;
if（p==1）//邻接信息
{
g.v[q][g.n].path=-1;
printf（"请输入%s和%s间的距离\n",g.name[q],g.name[g.n]）;
scanf（"%d",&dis）;
g.v[q][g.n].distance=dis;
g.v[g.n][q].distance=dis;
}
else
{
g.v[q][g.n].distance=99999;//99999表示距离的无限大值
g.v[g.n][q].distance=99999;//99999表示距离的无限大值
}
}
g.n++;
returng;
}//添加结束
MgraphInit（Mgraphg）//初始化一个邻接矩阵无向图
{
intq=0,p=0;
g.n=1;
printf（"请输入第一个城市的名称\n"）;
scanf（"%s",g.name[0]）;
for（q=0;qfor（p=0;p{
g.v[p][q].path=-2;
g.v[q][q].distance=0;
}
returng;
}//初始化结束
voidmain（）
{
inti,m=0;
Mgraphp;
do{
printf（"|__________________________________|\n"）;
printf（"|选择操作|\n"）;
printf（"|1.创建一个图|\n"）;
printf（"|2.添加一个新的城市|\n"）;
printf（"|3.修改现有城市的数据|\n"）;
printf（"|4.求最短路径|\n"）;
printf（"|5.退出程序|\n"）;
printf（"|__________________________________|\n"）;
scanf（"%d",&i）;
switch（i）
{
case1:
p=Init（p）;break;//初始化
case2:
p=ADD（p）;break;//添加城市
case3:
p=Modify（p）;break;//修改城市数据
case4:
Floyd（p）;break;//弗洛伊的算法
case5:
exit（0）;break;//退出程序
}
printf（"是否继续1：
继续0：
退出\n"）;
scanf（"%d",&m）;
system（"cls"）;
}while（m==1）;
}
课程设计总结：
开始拿到题后感觉很难，没有一点思绪，就借了一些数据结构与C语言设计方面的书看了一些才慢慢有点思路，于是就尝试开始编程序
在写程序的过程中总是会查课本去注意一些细节方面的问题，也让我懂得了即使是再小再细的东西在学习的过程中也要重视，深深体会到了细节可以决定成功与否的道理。
同时编程序的过程也让我掌握了一些没学过的知识并且也深深巩固了以前的知识。
这让我明白并且也给了我以后学这门专业的一方向：
经常找一些实用的问题去编，提高自己的专业知识同时也提高实践能力，而不只是光会纸上谈兵。
当我上机实践时，编译后出现了很多错误，开始耐下性一个一个检查，慢慢就灰心了。
编译过程让我明白自己要加强英语水平，同时也要注意细节，也要有耐性，对一些常见的错误要熟记，下次再出现同样错误就可以第一时间反映出来，可以节省一些时间。
总之这次课设受益匪浅，感受颇多，知道了自己在计算机方面的还了解的不多，以后会努力提高自身综合素质。
升级会员 