沈阳航空航天大学
课 程 设 计 报 告
课程设计名称：数据结构课程设计
课程设计
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目：最短路径求解
院（系）：计算机学院
专 业：计算机科学与技术(物联网方向)
班 级：
学 号：
姓 名：
指导教师：
学术诚信声明
本人声明：所呈交的
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的
材料
关于××同志的政审材料调查表环保先进个人材料国家普通话测试材料农民专业合作社注销四查四问剖析材料
。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。
本人签名: 日期： 2015 年 1 月 15 日
沈阳航空航天大学
课程设计任务
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
课程设计名称
数据结构课程设计
专业
计算机科学与技术（物联网方向）
学生姓名
班级
学号
题目名称
最短路径求解
起止日期
2015
年
1
月
5
日起至
2015
年
1
月
16
日止
课设内容和要求：
从键盘输入一个图，节点代表城市，节点间的边代表城市间距离，现指定图中任意两个城市，求出连接这两个城市的最短行走路线。
参考资料：
算法与数据结构，严蔚敏、吴伟民，清华大学出版社，2006
C程序设计，谭浩强，清华大学出版社，2010
教研室审核意见： 教研室主任签字：
指导教师（签名）
2015
年
1
月
15
日
学 生（签名）
年
月
日
目 录
沈阳航空航天大学 I
学术诚信声明 I
一 课程设计目的和要求 - 1 -
1.1 课程设计目的 - 1 -
1.2 课程设计的要求 - 1 -
二 概要设计 2
三 详细设计及主要算法流程图 2
3.1建立图的存储结构 2
3.2单源最短路径 3
3.3任意一对顶点之间的最短路径 4
四 运行与分析 6
五 参考文献 9
六 附 录（关键部分程序清单） 9
一 课程设计目的和要求
1.1 课程设计目的
(一) 根据算法设计需要，掌握图的数据表示方法；
(二) 掌握最短路径的迪杰斯特拉算法以及弗洛伊德算法；
(三) 学习独立撰写报告文档。
1.2 课程设计的要求
从键盘输入一个图，节点代表城市，节点间的边代表城市间距离，即用边的权值表示两个城市间的距离，首先以某个点为始点利用迪杰斯特拉算法求该点与其他点之间最短路径，选择任意一对顶点，利用弗洛伊德算法求解两点间的最短路径，输出路径及路径长度。
二 概要设计
系统主要完成三个功能，建立图的存储结构，利用迪杰斯特拉算法求解单源最短路径，利用弗洛伊德算法求解任意一对顶点间最短路径，将路径及其路程输出。
利用迪杰斯特拉算法求解单源最短路径
建立图的存储结构
主函数
利用弗洛伊德算法求解任意一对顶点间最短路径
三 详细设计及主要算法流程图
3.1建立图的存储结构
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。
注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点
的信息）。
邻接矩阵的存储结构：
#define MVNum 100 //最大顶点数
typedef struct
{
VertexType vexs[MVNum];//顶点数组，类型假定为char型
Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为int型
}MGraph;
注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。
3.2单源最短路径
单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。
迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。
算法思想：设有向图G=(V,E)，其中V={1,2，……n}，cost是表示G的邻接矩阵，
cost[i][j]表示有向边
的权。若不存在有向边，则cost[i][j] 的权为无穷大（这里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
从源点到其它各顶点当前的最短距离，其初值为dist[i]= cost[i][j]，i=2，……n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w] 的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。
最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。
3.3任意一对顶点之间的最短路径
任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(V≠W)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。
费洛伊德算法的基本思想：假设求从Vi到Vj的最短路径。如果存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较路径和的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径< vi,…,v2,…,vj>，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推……直至顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。
四 运行与分析
测试实例1：利用如下图所示的有向图来测试
13
17
61
74
76
32
64
56
26
45
测试实例2：利用下图求交通网络图（无向图）的最短路径。
695
349
511
812
1579
651
2368
1385
实例1运行结果：
实例2运行结果：
五 参考文献
(一) 算法与数据结构，严蔚敏、 吴伟民，清华大学出版社，2006
(二) C程序设计，谭浩强，清华大学出版社，2010
六 附 录（关键部分程序清单）
#include
#include
#define MVNum 100
#define Maxint 32767
enum boolean{FALSE,TRUE};
typedef char VertexType;
typedef int Adjmatrix;
typedef struct
{
VertexType vexs[MVNum];//顶点向量
Adjmatrix arcs[MVNum][MVNum];//邻接矩阵
}MGraph;//图的数据类型
int D1[MVNum],p1[MVNum];
int D[MVNum][MVNum],p[MVNum][MVNum];
void CreateMGraph(MGraph * G,int n,int e)//创建图的存储结构，n为顶点个数，e为边数
{
int i,j,k,w;//w为两点间的权值
for(i=1;i<=n;i++)
G->vexs[i]=(char)i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;//初始化设置，认为两点间距离无限大
printf("输入%d条边的i.j及w:\n",e);
for(k=1;k<=e;k++){
scanf("%d,%d,%d",&i,&j,&w);
G->arcs[i][j]=w;
}
printf("有向图的存储结构建立完毕！\n");
}
void Dijkstra(MGraph *G,int v1,int n)//利用迪杰斯特拉算法求解以v1为起点的单源最短路径
{
int D2[MVNum],p2[MVNum];//D2[MVNum]为带权长度，p2[MVNum]为最短路径
int v,i,w,min;
enum boolean S[MVNum];
for(v=1;v<=n;v++){
S[v]=FALSE;//S表示v是否是已找到的终点
D2[v]=G->arcs[v1][v];
if(D2[v]arcs[v][w]arcs[v][w];
p2[w]=v;
}
}
printf("路径长度 路径\n");
for(i=1;i<=n;i++)//输出结果
{
printf("%5d",D2[i]);
printf("%5d",i);v=p2[i];
while(v!=0)
{
printf("<-%d",v);
v=p2[v];
}
printf("\n");
}
}
void Floyd(MGraph *G,int n)//利用弗洛伊德算法求解n个顶点的图的最短路径
{
int i,j,k,v,w;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if( G->arcs[i][j]!=Maxint)
p[i][j]=j;
else
p[i][j]=0;
D[i][j]=G->arcs[i][j];
}
for(k=1;k<=n;k++)
浙公网安备 33021202002483