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

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

《数据结构课程设计报告Dijkstra算法求最短路径.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告Dijkstra算法求最短路径.docx（22页珍藏版）》请在冰点文库上搜索。

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

中南大学

《数据结构》课程设计

题目第9题Dijkstra算法求最短路径

学生姓名XXXX

指导教师XXXX

学院信息科学与工程学院

专业班级XXXXXXX

完成时间XXXXXXX

第1章问题分析与任务定义---------------------------------------------------------------------3

1.1课程设计题目-----------------------------------------------------------------------------3

1.2原始数据的输入格式--------------------------------------------------------------------3

1.3实现功能-----------------------------------------------------------------------------------3

1.4测试用例-----------------------------------------------------------------------------------3

1.5问题分析-----------------------------------------------------------------------------------3

第2章数据结构的选择和概要设计------------------------------------------------------------4

2.1数据结构的选择--------------------------------------------------------------------------4

2.2概要设计-----------------------------------------------------------------------------------4

第3章详细设计与编码-----------------------------------------------------------------------------6

3.1框架的建立---------------------------------------------------------------------------------6

3.2点结构体的定义---------------------------------------------------------------------------7

3.3创立带权值有向图------------------------------------------------------------------------8

3.4邻接矩阵的显示---------------------------------------------------------------------------9

3.5递归函数的应用---------------------------------------------------------------------------10

3.6Dijkstra算法实现最短路径--------------------------------------------------------------10

第4章上机调试------------------------------------------------------------------------------------11

4.1记录调试过程中错误和问题的处理---------------------------------------------------11

4.2算法的时间课空间性能分析------------------------------------------------------------11

4.3算法的设计、调试经验和体会---------------------------------------------------------11

第5章测试结果-----------------------------------------------------------------------------------12

第6章学习心得体会-----------------------------------------------------------------------------12

第7章参考文献-----------------------------------------------------------------------------------12

附录------------------------------------------------------------------------------------------------------12

第1章问题分析与任务定义

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找到的最短路径如何输出。

第2章数据结构的选择和概要设计

1.数据结构的选择：

在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。

由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。

在此我选用邻接矩阵的存储结构。

采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。

不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。

以邻接矩阵存储有向图。

2.概要设计

2.1对于最短路径问题：

最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：

（1）从某源点到其余各顶点之间的最短路径。

（2）每一段顶点之间的最短路径

在这里我们解决第一类问题。

2.2Dijkstra算法用于求最短路径：

Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。

算法建立一个顶点集合S，初始时该集合只有源点V0，然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。

2..3Dijkstra算法思想

设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]

5）重复操作2）、3）、4），直到全部顶点加入到S中。

2.4实现流程

在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。

当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。

程序流程图：

（1）输入顶点个数n，边的条数，初始化邻接矩阵。

（2）初始化所每条边的权值与D[h]中

（3）①找出v0到图中其他各点的最小值

②经过改最小值的点到除它外其他各点的最小值

③直到s中的所有值全部被处理过，

（4）输出各最短路径的长度D[w]

算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。

第3章详细设计和编码

3.1框架的建立

typedefcharVertexType;//定义图的顶点为字符型

typedefintVRType;//顶点关系类型

typedefintInfoType;//该弧相关信息

typedefstructArcCell{

VRTypeadj;//权值

InfoType*info;//弧相关信息的指针

}ArcCell;

typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//一维数组，存储顶点

ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵：

二维数组，存储边和弧

intvexnum,arcnum;//图的当前顶点数和弧数

}MGrph;//邻接矩阵表示的图

3.1.1顶点的定义typedefcharVertexType;//定义图的顶点为字符型顶点的最大个数25

3.1.2ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大3000表示。

3.2点结构体的定义

/*确定位置函数*/

intLocateVex（MGrph*G,VertexTypev）

{

intj,b;

for（b=0;bvexnum;b++）//在所有顶点中寻找

if（G->vexs[b]==v）//找到所找的顶点在b位置

{

j=b;

break;

}//if

return（j）;

}//LocateVex

3.3创立带权值有向图

首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。

/*有向图的建立*/

voidCreat_YG（MGrph*G）

{

inti,k,j,n;

VertexTypev1,v2;

intw=1;

printf（"请输入顶点个数和弧数如括号里的方式（3,3）:

"）;//读入顶点个数和弧的个数

scanf（"%d,%d",&G->vexnum,&G->arcnum）;//读出边和弧的信息

printf（"\n"）;//换行输出

for（i=0;ivexnum;i++）

{

printf（"请输入图的第%d个顶点:

",w）;//输入指定的顶点

w++;

fflush（stdin）;

scanf（"%c",&G->vexs[i]）;

printf（"\n"）;

}

for（i=0;ivexnum;i++）

for（j=0;jvexnum;j++）

{

G->arcs[i][j].adj=INFINITY;

G->arcs[i][j].info=NULL;

}

for（k=0;karcnum;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;//边的权值赋为1，如需要权值操作则相应修改一下即可

G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入，在这里我设置为空

}//第二个for

getchar（）;

}//Creat_YG

voidjuzhen（MGrph*G）{//用矩阵来存储并显示出结果

inti,j,k;

printf（"邻接矩阵显示：

\n"）;

printf（"\t"）;

for（i=0;ivexnum;i++）

printf（"\t%5c",G->vexs[i]）;

for（j=0;jvexnum;j++）

{

printf（"\n\n"）;

printf（"\t\%5c",G->vexs[j]）;

for（k=0;kvexnum;k++）

{

if（G->arcs[j][k].adj

printf（"\t%5d",G->arcs[j][k].adj）;

elseprintf（"\t3000"）;//无权值的直接输出最大值

}

}

3.4邻接矩阵的显示

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

voidjuzhen（MGrph*G）{//用矩阵来存储并显示出结果

inti,j,k;

printf（"邻接矩阵显示：

\n"）;

printf（"\t"）;

for（i=0;ivexnum;i++）

printf（"\t%5c",G->vexs[i]）;

for（j=0;jvexnum;j++）

{

printf（"\n\n"）;

printf（"\t\%5c",G->vexs[j]）;

for（k=0;kvexnum;k++）

{

if（G->arcs[j][k].adj

printf（"\t%5d",G->arcs[j][k].adj）;

elseprintf（"\t3000"）;//无权值的直接输出最大值

}

}

}

3.5递归函数应用

3.5.1思想是patn[]数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱

voidShort（MGrph*G,intpath[],inti,intw）{

//递归函数是用来输出从源点出发到终点之前的顶点

//思想是patn[]数组来表示前驱顶点的位置，然后递归输出每个顶点的前驱

intk;

k=path[i];

if（k!

=w）Short（G,path,k,w）;

printf（"%c,",G->vexs[k]）;//输出k位置的顶点值

}

3.6Dijkstra算法实现最短路径

设图以邻接矩阵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添加到路径中。

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

第4章上机调试

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到每个结点的最短路径时，导致无法具体记录经过的顶点数，只能记录源点、终点前一顶点以及终点。

所以本程序在输出最短路径时有较大的瑕疵，还需进一步修改。

第5章测试结果

5.1测试结果：

注意问题：

1、输入顶点个数：

最大不超过25，请输入罗马数字，若输入其他符号，无意义；

2、以“字母字母数字”的格式输入图的信息，输入第一个字母为原点，第二个字母为终点，输入“数字”为权值，最后输入一个“字母”为顶点输入。

输入完成；

3、在输入完成后，屏幕显示邻接矩阵与最短路径。

第6章学习心得体会

通过对本次课程设计的学习与交流，使我学习到一部分很重要的关于编程方面思想，同时也获得了部分学习其他学科的方法。

学习重在于体会，体会这种学科给我带来的思考，给我带来由浅入深的演算心得。

做一次课程设计，不仅仅是为了完成某项任务，而在于是否能从这次任务中总结出一些处理同类任务的方法和技巧。

每次全力的付出，都会有或多或少的收获。

通过对本次课程设计涉及的问题的分析和处理，了解到学习数据结构对编程的技巧和思想方法。

以前也了解过数据结构相关的书籍，但没有深入的学习，本次上机课程设计从选题上也把学习的方法应用其中，在编程时算法的理解和分析十分重要，首先的弄懂它的基本框架，用什么来算法来实现，最后通过查找部分资料，修改调试，总结心得，就是一种进步。

第7章参考文献

6.1：

严蔚敏吴伟明编著的《数据结构》（C语言版）

6.2：

杨晓波主编王弘王聪华胡永副主编的

《数据结构实验指导》（C语言版）

附件：

#include

#include

#defineMAX_VERTEX_NUM25//最大顶点个数

#defineINFINITY3000//最大值

typedefcharVertexType;//定义图的顶点为字符型

typedefintVRType;//顶点关系类型

typedefintInfoType;//该弧相关信息

typedefstructArcCell{

VRTypeadj;//权值

InfoType*info;//弧相关信息的指针

}ArcCell;

typedefstruct{

VertexTypevexs[MAX_VERTEX_NUM];//一维数组，存储顶点

ArcCellarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵：

二维数组，存储边和弧

intvexnum,arcnum;//图的当前顶点数和弧数

}MGrph;//邻接矩阵表示的图

/*确定位置函数*/

intLocateVex（MGrph*G,VertexTypev）

{

intj,b;

for（b=0;bvexnum;b++）//在所有顶点中寻找

if（G->vexs[b]==v）//找到所找的顶点在b位置

{

j=b;

break;

}//if

return（j）;

}//LocateVex

/*有向图的建立*/

voidCreat_YG（MGrph*G）

{

inti,k,j,n;

VertexTypev1,v2;

intw=1;

printf（"请输入顶点个数和弧数如括号里的方式（3,3）:

"）;//读入顶点个数和弧的个数

scanf（"%d,%d",&G->vexnum,&G->arcnum）;//读出边和弧的信息

printf（"\n"）;//换行输出

for（i=0;ivexnum;i++）

{

printf（"请输入图的第%d个顶点:

",w）;//输入指定的顶点

w++;

fflush（stdin）;

scanf（"%c",&G->vexs[i]）;

printf（"\n"）;

}

for（i=0;ivexnum;i++）

for（j=0;jvexnum;j++）

{

G->arcs[i][j].adj=INFINITY;

G->arcs[i][j].info=NULL;

}

for（k=0;karcnum;k++）

{//输入各弧并构造邻接矩阵

printf（"请输入边的起点和终点和权值如（v1,v2,n）:

"）;//起始点和终点和两点之间对应的权值

fflush（s