当前位置:首页 >> 其它课程 >> 数据结构课程设计报告--Dijkstra算法求最短路径

数据结构课程设计报告--Dijkstra算法求最短路径


中南大学 《数据结构》课程设计





第 9 题 Dijkstra 算法求最短路径 XXXX XXXX 信息科学与工程学院 XXXXXXX XXXXXXX

学生姓名 指导教师 学 院

专业班级 完成时间

1

目录 第一章 问

题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章 数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章 详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra 算法实现最短路径--------------------------------------------------------------10 第四章 上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章 测试结果-----------------------------------------------------------------------------------12 第六章 学习心得体会-----------------------------------------------------------------------------12 第七章 参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12

2

第一章 问题分析与任务定义 1、课程设计题目:
1.1 题目:采 用 适 当 的 存 储 结 构 实 现 带 权 有 向 图 的 存 储 , 建 立 , 输 入 、 显 示 , 以 及 使 用 Dijkstra 算 法 , 寻 找 和 输 出 带 权 有 向 图 中 某 个 源 点 到其余各点的最短路径 1.2 要 求 :采 用 适 当 的 存 储 结 构 实 现 带 权 有 向 图 的 存 储 ,建 立 ,输 入 、 显 示 , 以 及 使 用 Dijkstra 算 法 。 1.3 具 体 任 务 :建立图的存储模块,建立图的输出模块,在建图后从单源点开 始求最短路径,并显示出来。

2.原始数据的输入格式
2.1 建图:2.1.1 数字 2.2 显示:2.2.1 数字+逗号+数字+回车 2.2.2 字母+回车

3.实现功能
3.1 建立有向图 3.2 显示存储的有向图 3.3 显示从顶点到其他各个顶点的最短路径和是否存在路径

4.测试用例
4.1 正确数据:输入顶点;边值信息 输出结果:最短路径是否存在,存在的情况最短路径是多少,其次是不存 在。

5.问题分析
实现本程序要解决以下几个问题: 5.1 如何存储一个有向图。 5.2 如何在界面中输出该有向图。 5.3 如何定义起始源点。 5.4 如何选择出最短路径。 5.5 找到的最短路径如何输出。

3

第二章 数据结构的选择和概要设计
1.数据结构的选择:
在图的结构中,任意两个顶点之间都可能存在关系,比线性表和树要复 杂。 由于不存在严格的前后顺序,因而不能采用简单的数组来存储图;另一方 面,如果采用链表,由于图中各顶点的度数不尽相同,最小度数和最大度数 可能相差很大,如果按最大度数的顶点来设计链表的指针域,则会浪费很多 存储单元,反之,如果按照各个顶点设计不同的链表结点,则会给操作带来 很大的困难。 在此我选用邻接矩阵的存储结构。采用邻接矩阵存储,很容易判断图中 两个顶点是否相连, 也容易求出各个顶点的度。不过任何事情都不是完美的, 采用邻接矩阵存储图时, 测试其边的数目,必须检查边二维数组的所有元素, 2 时间复杂度为 O(n ),这对于顶点很多而边较少的图(稀疏图)是非常不合 算的。 以邻接矩阵存储有向图。

2.概要设计
2.1 对于最短路径问题: 最短路径是在实际应用中非常有用的工具, 我们常见的两种最短路径 是: (1)从某源点到其余各顶点之间的最短路径。 (2)每一段顶点之间的最短路径 在这里我们解决第一类问题。 2.2 Dijkstra 算法用于求最短路径: Dijkstra 算法是按路径长度递增的次序逐步产生源点到其他顶点间 的最短路径。算法建立一个顶点集合 S,初始时该集合只有源点 V0,然后 逐步将已求得最短路径的顶点加入到集合中,直到全部顶点都在集合 S 中,算法结束。 2..3 Dijkstra 算法思想 设 cost[i,j]=0,S 为已经求得最短路径的顶点集合,distance[i]数 组的每个元素表示当前状态下源点 V0 到 Vi 的最短路径。算法如下: 1) 初始化:S={V0}, distance[i]=cost[0,i]。 2) 选择一个终点 Vj,满足 distance[j]=MIN{ distance[i]|Vi∈V-S}。 3)把 Vj 加入到 S 中。 4)修改 distance 数组元素,修改逻辑为对于所有不在 S 中的顶点 Vi. if(distance[j]+cost[i,j]<
4

distance[i])

{

distance[i]=

distance[j] ]+cost[i,j] } 5)重复操作 2) 、3) 、4) ,直到全部顶点加入到 S 中。 2.4 实现流程 在任意图中实现求最短路径问题, 第一步是要能成功的在内存中输入 图的信息, 图的信息有两个, 一是顶点个数, 二是每两点之间的权值信息。 当建立图之后,对图进行遍历才能使用 Dijkstra 算法求出最短路径;在 完成了图的建立之后,用 Dijkstra 算法的思想,从单源点开始,求出到 各个顶点的最短路径,并能够实现显示功能。 程序流程图:

开始

输入顶点边个数

输入顶点名称

输入每条边的信息

创建图

返回每个结点 的位置

Dijkstra 算法的实现

D[w]<n

输出源点与其他点最短距离

结束

5

(1) 输入顶点个数 n,边的条数,初始化邻接矩阵。 (2)初始化所每条边的权值与 D[h]中 (3) ① 找出 v0 到图中其他各点的最小值 ② 经过改最小值的点到除它外其他各点的最小值 ③ 直到 s 中的所有值全部被处理过, (4) 输出各最短路径的长度 D[w] 算法的思想, 从单源点开始, 求出到各个顶点的最短路径, 并能够实现显示功能。

第三章 详细设计和编码
3.1 框架的建立
typedef char VertexType;//定义图的顶点为字符型 typedef int VRType; //顶点关系类型 typedef int InfoType;//该弧相关信息

typedef struct ArcCell{ VRType adj;//权值 InfoType *info;//弧相关信息的指针 }ArcCell; typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//一维数组,存储顶点 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 : 二维数组, 存储边和弧 int vexnum,arcnum;//图的当前顶点数和弧数 }MGrph; //邻接矩阵表示的图 3.1.1 顶点的定义 typedef char VertexType;//定义图的顶点为字符型 顶点的 最大个数 25 3.1.2ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 二维数组用于存放邻 接矩阵,每个位置代表的值为图中的权值,其余用无穷大 3000 表示。

3.2 点结构体的定义
/* 确定位置函数 int LocateVex(MGrph *G,VertexType v) { int j,b;
6

*/

for(b=0;b<G->vexnum;b++)//在所有顶点中寻找 if(G->vexs[b]==v)//找到所找的顶点在 b 位置 { j=b; break; }//if return(j); } //LocateVex

3.3 创立带权值有向图
首先输入该有向图的顶点数 n,然后依次输入各个顶点及边长(输入的顶点的序 号应该小于顶点的数目) 。
/* 有向图的建立 */ void Creat_YG(MGrph *G) { int i,k,j,n; VertexType v1,v2; int w=1; printf("请输入顶点个数和弧数 如括号里的方式(3,3):");//读入顶点个数和弧的个数 scanf("%d,%d",&G->vexnum,&G->arcnum);//读出边和弧的信息 printf("\n"); //换行输出 for(i=0;i<G->vexnum;i++) { printf("请输入图的第%d 个顶点:",w);//输入指定的顶点 w++; fflush(stdin); scanf("%c",&G->vexs[i]); printf("\n"); } for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) { G->arcs[i][j].adj=INFINITY; G->arcs[i][j].info=NULL; } for(k=0;k<G->arcnum;k++) {//输入各弧并构造邻接矩阵 printf("请输入边的起点和终点和权值如(v1,v2,n):");//起始点和终点和两点之间对 应的权值 fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&n); printf("\n"); i=LocateVex(G,v1);//确定 v1 的位置 j=LocateVex(G,v2);//确定 v2 的位置
7

G->arcs[i][j].adj=n;//边<v1,v2>的权值赋为 1,如需要权值操作则相应修改一下即可 G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入,在这里我设置为空 }//第二个 for getchar(); } //Creat_YG void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k; printf("邻接矩阵显示:\n"); printf("\t"); for(i=0;i<G->vexnum;i++) printf("\t%5c",G->vexs[i]); for(j=0;j<G->vexnum;j++) { printf("\n\n"); printf("\t\%5c",G->vexs[j]); for(k=0;k<G->vexnum;k++) { if(G->arcs[j][k].adj<INFINITY) printf("\t%5d",G->arcs[j][k].adj); else printf("\t 3000"); //无权值的直接输出最大值 }

}

3.4 邻接矩阵的显示
在图的邻接矩阵显示中,分别利用 for 循环输出了矩阵的行列标,使矩阵很明了。

void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k; printf("邻接矩阵显示:\n"); printf("\t"); for(i=0;i<G->vexnum;i++) printf("\t%5c",G->vexs[i]); for(j=0;j<G->vexnum;j++) { printf("\n\n"); printf("\t\%5c",G->vexs[j]); for(k=0;k<G->vexnum;k++) {
8

if(G->arcs[j][k].adj<INFINITY) printf("\t%5d",G->arcs[j][k].adj); else printf("\t 3000"); //无权值的直接输出最大值

} } }

3.5 递归函数应用
3.5.1 思想是 patn[]数组来表示前驱顶点的位置,然后递归输出每个顶点的前驱
void Short(MGrph *G,int path[],int i,int w){ //递归函数是用来输出从源点出发到终点之前的顶点 //思想是 patn[]数组来表示前驱顶点的位置,然后递归输出每个顶点的前驱 int k; k=path[i]; if(k!=w) Short(G,path,k,w ); printf("%c,",G->vexs[k]);//输出 k 位置的顶点值 }

3.6 Dijkstra 算法实现最短路径
设图以邻接矩阵 cost 存储,矩阵中各元素的值为各边的权值。顶点间无边 时其对应权值用无穷大表示。从顶点 V0 到其它各顶点间的最短路径的具体步骤 如下: a) 变量定义: 定义整型数组 S[],这是一个顶点集合,初始时该集合只有源点 v0,然后 逐步将以求得最短路径的顶点加入到该集合中, 直到全部顶点都在集合 S 中,算法结束。定义两个整型变量 dis、mindis 均用来标志图中最短的 那一条路径。 b) 初始化: 初 始 化 dist 数 组 的 值 即 为 cost 数 组 中 存 放 的 权 值 。 dist[i]=cost[v0][i] 初 始 化 求 到 每 个 顶 点 的 最 短 路 径 时 都 经 过 v0 顶 点 。 path[i].pnode[0]=v0 初始化记录经过的顶点数都为 0。 path[i].num=0; 初始化顶点集合 s 为空,即还未开始。 s[i]=0; c) 源点的选择: 将 v0 顶点加入到顶点集合 s 中。 s[v0]=1 d) 利用 for 循环选择一个终点 Vj,使其满足 V0 到 Vj 距离最短,同时将 Vj 加入集合 S 中。 e) 根据 j 顶点调整当前的最短路径, 若满足 dist[i]> dist[j]+cost[j][i], 则修改 dist[i]的值。 同时 V0 到 Vi 的最短路径中经过的顶点数加 1,即 path[i].num++; 并 将 经 过 的 顶 点 存 入 数 组 pnode 即 path[i].pnode[path[i].num]=j f) 此时一趟求最短路径完毕,将终点 V1 添加到路径中。
9

g)

循环执行 d),e),f)操作,直到全部顶点加入到 S 中。

第四章 上机调试
4.1 记录调试过程中错误和问题的处理
1) 当输入格式不符合程序要求时,会出现循环 2) 当两顶点间没有路径时,权值为无穷大,但在本程序中只能用一个具体的数字 2000 代替抽象的无穷大。 3) 在程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况, 并对程 序规格说明作调整和改动。 4.2 算法的时间和空间性能分析 4.2.1 时间复杂度 对于 n 个顶点的有向图,求一个顶点到其他顶点的最短路径的时间为 O(n),调整最 短路径的循环共执行 n-1 次,是二层循环,所以,时间复杂度是 O(n2) 。 4.2.2 空间复杂度 采用邻接矩阵存储有向图, 应处理每两个顶点之间的关系, 所以空间复杂度为 O (n2) 。 4.3 算法设计、调试的经验和体会 Dijkstra 算法在上课的时候曾作为重点讲过, 所以在做查找最短路径的算法时很流畅, 但 是在输出最短路径的时候遇到了很大的阻力。因为在定义结点时,使用的是结构体数组,所 以当处理 V0 到每个结点的最短路径时,导致无法具体记录经过的顶点数,只能记录源点、 终点前一顶点以及终点。所以本程序在输出最短路径时有较大的瑕疵,还需进一步修改。

10

第五章 测试结果 5.1 测试结果:

11

注意问题: 1、输入顶点个数:最大不超过 25,请输入罗马数字,若输入其他符号,无意 义; 2、以“字母 字母 数字”的格式输入图的信息,输入第一个字母为原点,第 二个字母为终点,输入“数字”为权值,最后输入一个“字母”为顶点输 入。输入完成; 3、在输入完成后,屏幕显示邻接矩阵与最短路径。

第六章 学习心得体会
通过对本次课程设计的学习与交流,使我学习到一部分很重要的关于编程 方面思想,同时也获得了部分学习其他学科的方法。学习重在于体会,体会这 种学科给我带来的思考,给我带来由浅入深的演算心得。做一次课程设计,不 仅仅是为了完成某项任务,而在于是否能从这次任务中总结出一些处理同类任 务的方法和技巧。每次全力的付出,都会有或多或少的收获。通过对本次课程 设计涉及的问题的分析和处理,了解到学习数据结构对编程的技巧和思想方法。 以前也了解过数据结构相关的书籍,但没有深入的学习,本次上机课程设计从 选题上也把学习的方法应用其中,在编程时算法的理解和分析十分重要,首先 的弄懂它的基本框架,用什么来算法来实现,最后通过查找部分资料,修改调 试,总结心得,就是一种进步。

第七章 参考文献
6.1:严蔚敏 6.2:杨晓波 吴伟明 编著的《数据结构》 (C 语言版) 主编 王 弘 王聪华 胡 永 副主编的
12

《数据结构实验指导》 (C 语言版) 附件:
#include<stdio.h> #include<stdlib.h> #define MAX_VERTEX_NUM 25 //最大顶点个数 #define INFINITY 3000//最大值 typedef char VertexType;//定义图的顶点为字符型 typedef int VRType; //顶点关系类型 typedef int InfoType;//该弧相关信息

typedef struct ArcCell{ VRType adj;//权值 InfoType *info;//弧相关信息的指针 }ArcCell; typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//一维数组,存储顶点 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 :二维数组,存 储边和弧 int vexnum,arcnum;//图的当前顶点数和弧数 }MGrph; //邻接矩阵表示的图

/* 确定位置函数 */ int LocateVex(MGrph *G,VertexType v) { int j,b; for(b=0;b<G->vexnum;b++)//在所有顶点中寻找 if(G->vexs[b]==v)//找到所找的顶点在 b 位置 { j=b; break; }//if return(j); } //LocateVex /* 有向图的建立 void Creat_YG(MGrph *G) { */

13

int i,k,j,n; VertexType v1,v2; int w=1; printf("请输入顶点个数和弧数 如括号里的方式(3,3):");//读入顶点个数和弧的个数 scanf("%d,%d",&G->vexnum,&G->arcnum);//读出边和弧的信息 printf("\n"); //换行输出 for(i=0;i<G->vexnum;i++) { printf("请输入图的第%d 个顶点:",w);//输入指定的顶点 w++; fflush(stdin); scanf("%c",&G->vexs[i]); printf("\n"); } for(i=0;i<G->vexnum;i++) for(j=0;j<G->vexnum;j++) { G->arcs[i][j].adj=INFINITY; G->arcs[i][j].info=NULL; } for(k=0;k<G->arcnum;k++) {//输入各弧并构造邻接矩阵 printf("请输入边的起点和终点和权值如(v1,v2,n):");//起始点和终点和两点之间对 应的权值 fflush(stdin); scanf("%c,%c,%d",&v1,&v2,&n); printf("\n"); i=LocateVex(G,v1);//确定 v1 的位置 j=LocateVex(G,v2);//确定 v2 的位置 G->arcs[i][j].adj=n;//边<v1,v2>的权值赋为 1,如需要权值操作则相应修改一下即可 G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入,在这里我设置为空 }//第二个 for getchar(); } //Creat_YG void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,j,k; printf("邻接矩阵显示:\n"); printf("\t"); for(i=0;i<G->vexnum;i++) printf("\t%5c",G->vexs[i]); for(j=0;j<G->vexnum;j++) {
14

printf("\n\n"); printf("\t\%5c",G->vexs[j]); for(k=0;k<G->vexnum;k++) { if(G->arcs[j][k].adj<INFINITY) printf("\t%5d",G->arcs[j][k].adj); else printf("\t 3000"); //无权值的直接输出最大值 }

} } void Short(MGrph *G,int path[],int i,int w){ //递归函数是用来输出从源点出发到终点之前的顶点 //思想是 patn[]数组来表示前驱顶点的位置,然后递归输出每个顶点的前驱 int k; k=path[i]; if(k!=w) Short(G,path,k,w ); printf("%c,",G->vexs[k]);//输出 k 位置的顶点值

} void ShortestPath(MGrph *G,int w){ //Dijkstrs 算法应用 int i,k,m,n,min; int final[30],path[30],D[30]; //定义三个数组,final[]标记该顶点是否在最短路径上 //path[]用来记录顶点的前驱顶点的位置, D[]是用来记录从源点到该点的最短路径长度 for(i=0;i<G->vexnum;i++) { path[i]=w;//首先把所有顶点的前驱顶点的位置赋值为 w 位置,也就是源点的位置 final[i]=0;//这是一个标记数组,一开始所有顶点位置对应的数组值全部标记为 0 D[i]=G->arcs[w][i].adj;//D[]是用来记录最短路径的长度,一开始把所有顶点到源点 的的距离赋值给它 } D[w]=0;final[w]=1;path[w]=-100;//源点位置的 D[w]为 0,final[w]=1 标记已经入集合, path[w]=-100,表示该前驱为-100 for(m=1;m<G->vexnum;m++) { min=INFINITY;//首先赋值为机内最大值 for(k=0;k<G->vexnum;k++)
15

{ if(!final[k]) if(D[k]<min) { i=k; min=D[k];//最短路径长度 } } final[i]=1; for(n=0;n<G->vexnum;n++) if(!final[n]&&(min+G->arcs[i][n].adj)<D[n]) { D[n]=min+G->arcs[i][n].adj; path[n]=i; }//if } //for for(m=0;m<G->vexnum;m++){ if(final[m]==1&&m!=w) {printf("\t 从 %c 到 %c 的 最 短 路 径 长 度 为 : %d\t 路 径 是 : ",G->vexs[w],G->vexs[m],D[m]);//输出最大值时则表示两点之间没有最短路径 Short(G,path,m,w); printf("%c",G->vexs[m]); printf("\n"); } else printf("\t 从%c 到%c 没有不存在路径!\n",G->vexs[w],G->vexs[m]);//判断是否 存在最短路径 } }

main(){ MGrph m; VertexType ch; int j; Creat_YG(&m); juzhen(&m); printf("\n 请输入要开始的顶点:"); scanf("%c",&ch); j=LocateVex(&m,ch); getchar(); ShortestPath(&m,j);
16

getchar(); }

17


更多相关文档:

数据结构课程设计报告--Dijkstra算法求最短路径

中南大学 《数据结构课程设计 题 目 第 9 题 Dijkstra 算法求最短路径 XXXX XXXX 信息科学与工程学院 XXXXXXX XXXXXXX 学生姓名 指导教师 学院 专业班级 完成...

数据结构课程设计报告_最短路径C++

数据结构课程设计报告_最短路径C++_工学_高等教育_教育专区。青岛理工大学琴岛...Dijkstra 算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详 ...

《数据结构课程设计》最短路径问题实验报告

数据结构课程设计最短路径问题实验报告_电脑基础知识_IT/计算机_专业资料。...最短路径 Dijkstra算法 ... 5页 1下载券 数据实验报告书 图的应用... 9...

数据结构课程设计报告-最短路径算法-二叉树的三种遍历

数据结构课程设计报告-最短路径算法-二叉树的三种遍历_计算机软件及应用_IT/...最初对于最短路径算法,我首先想到的是 Dijkstra 算法,但后来发现 Dijkstra 算法...

课程设计_最短路径算法

沈阳航空航天大学 课程设计报告 课程设计名称:数据结构课程设计 课程设计题目:最...编写算法能够建立带权图, 并能够用 Dijkstra 算法求该图的最短路径。 2. ...

最短距离问题数据结构课程设计报告

数据结构课程设计报告题目:北海公园主要游览景点之间最短距离问题一、课程设计题目...(path,start,VT); // 用 Dijkstra 算法,求一个景点到其他景点间的最短路径...

数据结构课程设计之最短路径

长沙民政职业技术学院《数据结构》单元设计报告 数据...Dijkstra) 、弗洛伊德(Floyd) 1 引 言 本单元设计...产生最短路径算法:把 V 分成两组: (1)S:已求...

数据结构:单元最短路径,Dijkstra算法_实验报告

数据结构实验报告实验十一:最短路径实验报告姓名:戴铁泉 班级:物联 1001 班 学号:20101410305 完成日期:2012.05.23 实验目的:给定带权图 G 和源点 V,求从 V...

数据结构实验报告最短路径

数据结构实验报告最短路径_IT/计算机_专业资料。HUNAN UNIVERSITY 课程实习报告 ...设计 算法的具体步骤 建立以票价为权的邻接矩阵,用 Dijkstra 算法求最短路径...

Dijkstra最短路径算法课程设计

一般 情况下,假设 S 为已求得最短路径的终点的集合,则可证明:下一条最 短...数据结构课程设计报告--... 暂无评价 17页 免费 Dijkstra 最短路径算法 6页 ...
更多相关标签:
dijkstra最短路径算法 | 数据结构dijkstra算法 | 数据结构最短路径算法 | 单源最短路径dijkstra | dijkstra最短路径 | dijkstra最短路径理解 | dijkstra最短路径例题 | dijkstra求最短路径 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com