数据结构课程设计报告 迪杰斯特拉算法的实现.docx
《数据结构课程设计报告 迪杰斯特拉算法的实现.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告 迪杰斯特拉算法的实现.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告迪杰斯特拉算法的实现
数据结构课程设计报告
迪杰斯特拉算法的实现
班级：
软件1408
学号：
1130505140825
姓名：
马宏伟
指导教师：
石老师
完成时间：
2012年7月5日
题目:
Dijkstra算法的实现
一、问题分析和任务定义
1.1题目：
对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法。
1.2要求：
对所设计的图的数据结构，提供必要的基本功能。
1.3具体任务：
建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出最短路径长度及路径途径！
2、实现功能：
2.1建立有向图
2.2在建立好的有向图中，显示出来从源点到其他各个顶点的最短路径长度及路径途径。
3、测试用例：
3.1正确数据：
a）顶点：
3；边值信息：
012；103；125；216；000；
b）顶点：
0；边值信息：
000；
3.2错误数据：
a）顶点：
#；
b）顶点：
3；边值信息：
01#；
3.3参考用图：
图1
图1.有向图
问题分析:
题目要求选择合适的数据结构表示图，本程序邻接矩阵存储结点和弧等图的有关信息
对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其他各顶点（称为终点）有无路径？
最短路径是什么？
路径长为多少？
问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。
对邻接矩阵arsc[n][n]中的每一个元素只能有三种情况：
①当顶点i到j无边时，distance[j]=MAX;
②当顶点i到j有边且权值为edges[i][j]时，distance[j]=edges[i][j];
③当顶点i到就经过t有最短路径时，distance[j]=distance[t]+edges[t][j];
由于题目中没有规定输出格式，本程序以顶点序号的形式将最短路径输出到终端上去，并输出该最短路径的长度及路径途径。
二、数据结构的选择和概要设计
1）数据存储结构
以邻接矩阵存储有向图，如图2中有向图G所示，其邻接矩阵为图3edges。
图2.有向图图3.矩阵edges
有向图的邻接矩阵arcs[i][j]定义为intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
2）概要设计
对用邻接矩阵表示的有向图，从某一顶点出发（称为源点）到该图其他各顶点（称为终点）有无路径？
最短路径是什么？
路径长为多少？
问题要求写一个程序从有向网中的某一顶点出发找出该顶点到其余各顶点的最短路径。
对邻接矩阵edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]中的每一个元素只能有三种情况：
①当顶点i到j无边时，distance=MAX;②当顶点i到j有边且权值为edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]时，distance[j]=edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM].③当顶点i到就经过t有最短路径时，distance[j]=distance[t]+edges[t][j];
建立图的表示模块，顶点的插入和删除操作模块；在建立图之后从单源点开始求最短路径，并显示出来！
流程图如图4
图4.程序流程图
（2）设计表示法
（1）函数调用关系如图下图所示。
（2）函数接口说明。
voidshortpath_DIJ（MGraph*mg,chari）
VERTEXvexs[MAX_VERTEX_NUM];
intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
charpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
intdistance[MAX_VERTEX_NUM];
/*求n个顶点，邻接矩阵为edges，从源点i到各顶点的最短路径，distance[]记载从源点到其余各顶点的最短路径长度,path[]为最短路径途径,数组vexs[]用来存储顶点，
（3）各部分的函数和各函数之间的关系
采用邻接矩阵表示法，构造有向图
typedefstructVERTEX//定义顶点类型
typedefstructMGraph//定义图的类型
MGraph*create_MGraph（）//采用邻接矩阵创建有向图
voidshortpath_DIJ（MGraph*mg,chari）用Dijkstra算法求有向图的mg的i顶点到其余顶点的最短路径
voidmain（）
（4）实现注释
（1）系统限定邻接矩阵的阶n不超过max；
（2）为方便起见，系统假设有向网中边的权为整型数；
（3）若有向网中顶点i到j之间无边，则取值max。
Dijkstra算法描述如下：
（1）输入顶点个数n，邻接矩阵edges和源点序号i。
（2）送初值：
将i加入第一组s[i]=0；令distance[j]=edges[i][j];（j=0,1,2,…,n-1）
（3）重复n-1次做:
①在不属于s[]的顶点U中，选取具有最小distance[j]值的顶点V；
②将V加入s[]；
③对不属于s[]的顶点j做
distance[j]=min{distance[j];diatance[t]+edges[t][j]};
/*distance[j]取（distance[j],distance[t]+arcs[t][j]）两个数中的最小值*/
（4）输出各最短路径的长度distance[j]及相应的最短路径path[j]。
3、详细设计和编码
详细设计：
1）结点类型和指针类型
typedefstruct{//定义顶点类型
intnum;//顶点序号
chardata;//顶点信息
}VERTEX;
typedefstruct{//定义图的类型
intn;//顶点数目
inte;//弧的数目
VERTEXvexs[MAX_VERTEX_NUM];//一维数组，存储顶点
intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组，存储边或弧
}MGraph;
2）采用数组（邻接矩阵）表示法，构造有向网mg的基本算法
MGraph*create_MGraph（）{
inti,j,k,w,n,e;
charc;
MGraphmg1,*mg=&mg1;
printf（"**********请输入图的顶点数:
**********\n\t\t"）;//读入顶点个数
scanf（"%d",&n）;
printf（"**********请输入图中弧的数目:
********\n\t\t"）;//读入弧个数
scanf（"%d",&e）;
mg->n=n;
mg->e=e;
getchar（）;
printf（"\n*********输入顶点信息：
***********\n"）;//读入第i个顶点信息
for（i=0;iscanf（"%c",&c）;
getchar（）;
mg->vexs[i].data=c;
mg->vexs[i].num=i;//指定顶点的序号
}
for（i=0;ifor（j=0;jmg->edges[i][j]=max;//先把所以的边置空
printf（"请输入弧的信息，包括两个顶点及弧的权值：
\n"）;
for（i=0;iscanf（"%d%d%d",&j,&k,&w）;//读入边的信息
mg->edges[j][k]=w;
}
return（mg）;
}
3）主要算法基本思想。
单源最短路径问题采用迪杰斯特拉（Dijkstra）提出的按路径长度递增的次序产生最短路径的算法。
此算法把网中所有的顶点分成两组，分别用s[]]和U-s[]表示。
凡是以i为源点，已经确定了最短路径的终点属于s[]，s[]的初态应只包含i。
另一组U-s[]则是尚未确定最短路径的顶点集合。
U-s[]的初态应是除源点外的网中所有顶点的集合，按各顶点与i间的最短路径长度递增的次序，逐个把U-s[]中的顶点加入到s[]中，使得从i到s[]中各顶点的路径长度始终不大于从i到U-s[]中各顶点的路径长度。
它的初始状态即是邻接矩阵edges中第i行内各列的值。
显然，从源点到各顶点的最短路径中最短的一条路径应为
distance[j]=min{distance[j]（j=0,1，2，…，n-1）}
第一次求的最短路径必然是（i，j），这时顶点号j应从U-s[]中删除而并入s[]。
每当选出一个顶点号j并使之并入s[]后，就要修改U-s[]中各顶点的最短路径长度distance。
对于U-s[]中的某一个顶点j来说，其最短路径长度或者仍是（i，j），或者是（i，t，j），决不可能有其他选择，也就是说，若
distance[t]+edges[t][j]则修改distance[j]，使
distance[j]]=distance[t]+edges[t][j]]
当U-s[]组中各顶点的distance[]进行修改后，再从中挑选出一个路径长度路径最小的顶点，从U-s[]中删除后再并入s[]。
依次类推，就能求出所需的最短路径长度。
其中distance[]、U、s[]都定义为整型数组，数组s[]用以标记那些已经找到最短路径的顶点，若s[j]]为1表示已找到源点到顶点j的最短路径；若s[j]为0，则表示从源点到顶点j的最短路径尚未求得。
用Dijkstra算法求有向图的mg的i顶点到其余顶点j的最短路径
Dijkstra算法描述如下：
（1）输入顶点个数n，邻接矩阵edges和源点序号i。
（2）送初值：
将i加入第一组s[i]=0；令distance[j]=edges[i][j];（j=0,1,2,…,n-1）
（3）重复n-1次做:
①在不属于s[]的顶点U中，选取具有最小distance[j]值的顶点V；
②将V加入s[]；
③对不属于s[]的顶点j做
distance[j]=min{distance[j];diatance[t]+edges[t][j]};
/*distance[j]取（distance[j],distance[t]+arcs[t][j]）两个数中的最小值*/
（4）输出各最短路径的长度distance[j]及相应的最短路径path[j]。
4、上机调试
在调试过程中要特别注意函数调用时参数的传递问题，用数组名作为参数可进行传值调用，因而可将函数中的运行结果传递给主调函数，得出正确结果；再一个要注意的是输出结果时，循环结束的条件应为：
i==’#’时退出循环。
另外，上机前的静态检查不能忽视；程序的调试过程可暂时多加一些输出语句以便及时查看一下中间运行情况，并对程序规格说明作少量调整和改动。
算法的时间和空间性能分析
1时间复杂度
对于n个顶点的图，求一个顶点到其他顶点的最短路径，循环一次，加上修改最短路径的循环，是二层循环，所以，时间复杂度是O（n2）。
2空间复杂度
因为这个程序旨在求出最短路径，但是必然要涉及到图的存储，而对于Dijkstra算法弄清楚两个顶点之间的关系又显得尤为重要，所以，面对图的几种存储结构，用邻接表是比较合适的，不过它的缺点是占用空间大，复杂度为O（n2+m*n）。
5、测试结果及其分析
执行情况如下：
输入：
53/*顶点个数为5，弧数为3*/
01234/*顶点信息*/
012
023
121/*输入有向网中带权值的边及权值*/
0/*源点为0*/
1/*源点为1*/
#/*结束符*/
结果如图5所示。
6、用户使用说明
程序执行后，首先输出：
“输入图的顶点数：
”
输入图的顶点数后，输出：
“输入输入图中弧的数目：
”
输入输入图中弧的数目后，输出：
“输入顶点信息：
”
输入顶点信息后，输出：
“请输入弧的信息，包括两个顶点及弧的权值：
”（用空格键隔）
输入弧的信息，包括两个顶点及弧的权值后，输出：
“请输入指定顶点i（输入#号结束）：
”
输入起始顶点名称之后，输出结果：
图5.运行结果
7、参考文献
序号：
ISBN978-7-113-07628-3/TP.2201作者：
王昆仑李红书名：
数据结构与算法出版地：
北京市宣武区右安门西街8号出版社名称：
《中国铁道出版社》出版社年份2007
8、附录
//Dijkstra算法实现
#include"iostream"
#include"fstream"
#include"string"
#include
usingnamespacestd;
#defineMAX_VERTEX_NUM100//顶点的最大个数
#definemax65536//没有连接弧的顶点的距离
typedefstruct{//定义顶点类型
intnum;//顶点序号
chardata;//顶点信息
}VERTEX;
typedefstruct{//定义图的类型
intn;//顶点数目
inte;//弧的数目
VERTEXvexs[MAX_VERTEX_NUM];//一维数组，存储顶点
intedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//二维数组，存储边或弧
}MGraph;
MGraph*create_MGraph（）{
inti,j,k,w,n,e;
charc;
MGraphmg1,*mg=&mg1;
printf（"**********请输入图的顶点数:
**********\n\t\t"）;//读入顶点个数
scanf（"%d",&n）;
printf（"**********请输入图中弧的数目:
********\n\t\t"）;//读入弧个数
scanf（"%d",&e）;
mg->n=n;
mg->e=e;
getchar（）;
printf（"\n*********输入顶点信息：
***********\n"）;//读入第i个顶点信息
for（i=0;iscanf（"%c",&c）;
getchar（）;
mg->vexs[i].data=c;
mg->vexs[i].num=i;//指定顶点的序号
}
for（i=0;ifor（j=0;jmg->edges[i][j]=max;//先把所以的边置空
printf（"请输入弧的信息，包括两个顶点及弧的权值：
\n"）;
for（i=0;iscanf（"%d%d%d",&j,&k,&w）;//读入边的信息
mg->edges[j][k]=w;
}
return（mg）;
}
voidshortpath_DIJ（MGraph*mg,chari）{//图用邻居矩阵存储，i是源点
intinS[MAX_VERTEX_NUM];//辅助数组用来标志顶点是否已经在
//最短路径的顶点集合中
charpath[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//存放路径
intdistance[MAX_VERTEX_NUM];//到源点的距离
intm,n,j,wm;
intk=i-48;
for（m=0;m<（*mg）.n;m++）{//初始化各数组
inS[m]=0;
distance[m]=（*mg）.edges[k][m];
if（distance[m]{sprintf（path[m],"%d-->%d",k,m）;//将字符打入到字符串中
}
}
inS[k]=1;//顶点i加入到集合s中
for（m=0;m<（*mg）.n-1;m++）{//将最短路径顶点加入到s中
j=k;wm=max;
for（n=0;n<（*mg）.n;n++）//找当前的最短路径
if（inS[n]==0&&distance[n]j=n;wm=distance[n];
}
inS[j]=1;//j顶点加入到s中
for（n=0;n<（*mg）.n;n++）//根据顶点调整当前的最短路径
if（inS[n]==0&&distance[j]+（*mg）.edges[j][n]distance[n]=distance[j]+（*mg）.edges[j][n];
sprintf（path[n],"%s-->%d",path[j],n）;
}
}
for（j=0;j<（*mg）.n;j++）{
if（distance[j]==max）{
printf（"%d到%d的无路径\n",k,j）;
continue;
}
else
printf（"%d到%d的最短路径为%d（%s）\n",k,j,distance[j],path[j]）;
}
}
//****************************************************************************
voidmain（）{
MGraphmg1,*mg=&mg1;
VERTEXv11,v22,v33,*v1=&v11,*v2=&v22,*v3=&v33;
chari;
mg=create_MGraph（）;//图的创建
getchar（）;
printf（"请输入指定顶点i（输入#号结束）：
"）;//Djkstra法求最短路径
i=getch（）;
while（i!
='#'）{
shortpath_DIJ（mg,i）;
printf（"请输入指定顶点i（输入#号结束）：
"）;//Djkstra法求最短路径
i=getch（）;
}
}
升级会员 