数据结构最短路径.docx
《数据结构最短路径.docx》由会员分享，可在线阅读，更多相关《数据结构最短路径.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构最短路径
数据结构
设计说明书
单源点最短路径算法的实现
学生姓名
王文刚
学号
1418064056
班级
网络1402
成绩
指导教师
数学与计算机科学学院
年月日
课程设计任务书
20—20学年第学期
课程设计名称：
数据结构课程设计
课程设计题目：
单源点最短路径算法的实现
完成期限：
自年月日至年月日共2周
设计内容：
1.任务说明
2.要求
3.参考资料
指导教师：
教研室负责人：
课程设计评阅
评语：
指导教师签名：
年月日
摘要
设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。
本方法采用VC++作为软件开发环境，采用Dijkstar函数来求取顶点之间的最短路径。
，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。
关键词：
最短路径；Dijkstar；无向图;
1.目录中可以只有一级标题
2.页码右侧对齐页边距
3.本页不需要页码
4.以上内容仅作参考，具体章节由课程设计类型确定
1课题描述
随着交通的发展，人民生活水平的提高。
出门旅行变的越来越频繁，而且供暖也成为冬天不可或缺的内容。
为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。
那么如何找到最短路径呢？
由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。
而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。
这样可以广泛提高效率，容易理解。
2需求分析
3概要设计
3.1存储结构
一个图的邻接矩阵表示是唯一的。
图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。
因此，图的邻接矩阵的存储结构定义如下:
#defineMVNum50
typedefstruct{
VertexTypevexs[MVNum];
Adjmatrixarcs[MVNum][MVNum]；
}Mgraph;
图如下
图3.1无向图
abcdef
a∞34∞∞∞
b3∞∞155∞
c4∞∞312∞
d∞153∞∞8
e∞512∞∞6
f∞∞∞86∞
图2.1G的邻结矩阵
3.2算法描述
（1）Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。
迪杰斯特拉算法可用自然语言描述如下：
初始化S和D,置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE;D[v1]=0;
While（S集中的顶点数{
开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中;
S[v]=TRUE;更新当前最短路径及距离。
}
（2）Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。
（3）Dijkstra算法思想为：
设G=（V,E），G是带权无向图，V代表图中顶点集合，E代表图中含权重的边集合。
将全部顶点集合V分成两组，第一组为已求出最短路径的顶点集合，用S表示（初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合S中）；第二组为其余待确定最短路径的顶点集合，用U表示。
按最短路径长度的递增次序依次把U集合的顶点逐个加入到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。
算法的终止条件是集合U为空集，即集合U的顶点全部加入到集合S中。
（4）Maxint：
最大整数值，表示两个不能到达的顶点。
4详细设计
4.1功能模块图
如图4.1所示
求最短路径
Main函数
CreateMGraph函数
Pd函数
图4.1功能模块
4.2主函数
主函数流程图如图4.2
图4.2主函数
4.3pd函数
函数如图4.3所示
开始
结束
n>0&&e<=n（n-1）/2
输入n，e
（n是顶点数，e是边数）
N
Y
图4.3Pd函数
4.4CreateMGraph函数
createMGraph函数如图4.4所示
图4.4createMGraph函数
4.5Dijkstar函数
开始
v1到其余顶点集合v最短路径,带权长度D[MVnum],P[MVnum]
v=1
v<=n
置空sS[v]=FALSE,D2[v]=G..arcs[v1][v]
P[v]=0
若权值小与最大值D2[v]P[v]=v1
v=v+1
i<=n
初始化，v1顶点属于s集D2[v1]=0:
s[v1]
开始主循环，每次求得v1到某个v顶点的最短路径，并加到s中
当前所知离v1顶点最近距离min=Maxint
顶点变量w=1
w<=n
N
Y
Y
N
Y
Y
N
N
结束
v=ww顶点离v1更近
S[v]=TRUE;
w=w+1
w<=n
输出数据
i=i+1
!
S[w]&&D2[w]（!
S[w]&&（D2[v]+G.arcs[v][w]修改D2[w]，P2[w]D2[w]=D2[v]+G.arcs[v][w];P2[w]=v
w=w+1
i=1
i<=m
i=i+1
w=1
Y
Y
N
N
Y
N
5程序编码
#include
#include
#defineMVNum100
#defineMaxint32767
typedefcharVertexType;
typedefintAdjmatrix;
typedefenum{FALSE,TRUE}boolean;
typedefstruct{
VertexTypevexs[MVNum];
Adjmatrixarcs[MVNum][MVNum];
}MGraph;
intD1[MVNum],P1[MVNum];
intD[MVNum][MVNum],P[MVNum][MVNum];
intpd（MGraph*G,int&n,int&e）
{
while（（n>0）&&（e>n*（n-1）/2））{
printf（"你输入的顶点或边数不正确，请重新图中顶点个数和边数n，e:
"）;
scanf（"%d,%d",&n,&e）;
}
returnTRUE;
}
CreateMGraph（MGraph*G,intn,inte）
{
inti,j,k,w;
chara,b;
for（i=1;i<=n;i++）
G->vexs[i]=i;
for（i=1;i<=n;i++）
for（j=1;j<=n;j++）
G->arcs[i][j]=Maxint;
G->arcs[j][i]=Maxint;
printf（"输入%d条边的i,j及w:
\n",e）;
for（k=1;k<=e;k++）
{
fflush（stdin）;
scanf（"%c,%c,%d",&a,&b,&w）;
i=a-'a'+1;
j=b-'a'+1;
G->arcs[i][j]=w;
G->arcs[j][i]=w;
}
printf（"无向图的存储结构建立完毕!
\n"）;
}
voidDijkstra（MGraphG,intv1,intn）
{
intD2[MVNum],P2[MVNum];
intv,i,w,min;
booleanS[MVNum];//判断该点是否到过S中，即该点是否被遍历
for（v=1;v<=n;v++）
{
S[v]=FALSE;
D2[v]=G.arcs[v1][v];
if（D2[v]P2[v]=v1;
else
P2[v]=0;
}
D2[v1]=0;S[v1]=TRUE;
for（i=2;i<=n;i++）
{
min=Maxint;
for（w=1;w<=n;w++）
if（!
S[w]&&D2[w]{
v=w;min=D2[w];
}
S[v]=TRUE;
for（w=1;w<=n;w++）
if（!
S[w]&&（D2[v]+G.arcs[v][w]{
D2[w]=D2[v]+G.arcs[v][w];
P2[w]=v;
}
}
printf（"最短路径----------路径\n"）;
for（i=1;i<=n;i++）
{
printf（"%5d",D2[i]）;
printf（"%14c",i-1+'a'）;v=P2[i];
while（v!
=0）
{
printf（"<-%c",v-1+'a'）;
v=P2[v];
}
printf（"\n"）;
}
}
voidmain（）
{
MGraphG;
intn,e,v;
charch;
printf（"输入图中顶点个数和边数n，e:
"）;
scanf（"%d,%d",&n,&e）;
pd（&G,n,e）;
//scanf（"%d,%d",&n,&e）;
//n=r;
//e=a;
CreateMGraph（&G,n,e）;
while
（1）
{
printf（"求最短路径，输入开始点v:
"）;
fflush（stdin）;
scanf（"%c",&ch）;
v=ch-'a'+1;
Dijkstra（G,v,n）;
}
}
6程序的调试与测试
调试如图6.1所示
输入：
2,5
a,b,5
a,c,15b,c,6b,d,2c,d,10
ab
图6.1
7总结
本次课程设计涉及到的范围很广，让我能够比较系统的对C语言和数据结构进行一次整理和复习。
同时有了很多的体会和经验。
在这次课程设计中我体会到C语言超强的逻辑性，能够熟练使用的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，在编写程序过程中要灵活应用。
一开始信息是不能重复查询也就是说，
整个设计过程中，遇到了很多问题，例如查询一次后退出重新运行才可以不能连续查询后来添加了一个简单的while（）语句就实现了二次查询这次“求解最优路径”的课题，让我明白很多不知道的知识内容，对求解最优路径有了进一步的了解和认识。
最后感谢老师布置给我们的任务，我会更加努力的学好这方面的知识，编写出更有价值的程序。
最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径（这里特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。
在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。
参考文献
[1]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：
清华大学出版社,2002
[2]李春葆.数据结构（C语言版）习题与解析[M].北京：
清华大学出版社,2002
[3]钱能.C++程序设计教程[M].北京：
清华大学出版社,2003
升级会员 