Dijkstra算法的实现-数据结构与算法课程设计报告

合肥学院计算机科学与技术系课程设计报告2009～2010学年第2学期课程数据结构与算法课程设计名称Dijkstra算法的实现学生姓名张睿辰学号0804012044专业班级08计科(2)班指导教师王昆仑张贯虹2010年6月Dijkstra算法的实现一、问题分析与任务定义1、课程设计题目：1.1题目：对任意图，选择合适的数据结构表示图，在此基础上实现求解最短路径的Dijkstra算法1.2要求：设计合理的数据结构存储图，简单有效的实现Dijkstra算法。1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来！2、原始数据的输入格式：2.1建图模块：2.1.1数字2.2.2数字+空格+数字+空格+数字+回车2.3显示模块：回车3、实现功能：3.1建立有向图3.2显示存储的有向图3.3显示从顶点到其他各顶点的最短路径4、测试用例：4.1正确数据：a）顶点：3；边值信息：016；024；125；206；000；b）顶点：0；边值信息：000；输出结果：a)v0到v1的最短路径是6，v0到v2的最短路径是4b)没有最短路径4.2错误数据：a)顶点：ab）顶点：2；边值信息：036；044；135；000；c）顶点：3；边值信息：01a；输出结果：边值错误，请从新输入5、问题分析：实现本程序要解决以下几个问题：5.1如何存储一个有向图。5.2如何在界面中输出该有向图。5.3如何定义起始源点。5.4如何选择出最短路径。5.5找到的最短路径如何输出。二、数据结构的选择和概要设计1、数据结构的选择：在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，时间复杂度为O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。以邻接矩阵存储有向图，如图1中有向图G所示，其邻接矩阵为图2cost。图2.有向图图2.矩阵cost有向图的邻接矩阵cost[i][j]定义为intcost[n][n];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.153642451050201530315102005010∞45∞0155010∞200∞∞∞∞15∞20∞035∞∞∞∞300∞0∞3∞∞∞35if(distance[j]+cost[i,j]distance[i]){distance[i]=distance[j]]+cost[i,j]}5)重复操作2）、3）、4），直到全部顶点加入到S中。2.4实现流程在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。程序流程图：建图输入顶点与边值信息定义顶点个数开始Dijkstra算法求最短路径显示最短路径结束Dijkstra算法流程图：N设定变量，初始化dist[]数组，使其与cost[V0][i]相对应定义顶点V0与自身的距离为0;定义经过的顶点个数为0；定义顶点集合S[MAX]初始化数组S[i]，并规定i为顶点序号将起点V0加入数组首先初始最短路径mindis为无穷大；查找离顶点V0最近的顶点，并赋值距离给mindis=dist[j];根据找到的顶点寻找下一个路径最短的顶点S[u]，并记录最短路径dis=dist[u]+cost[j]；dis是否大于V0直接到S[u]的距离；最短路径为dist记录经过的顶点;j为寻找下一个顶点的变量添加顶点到最短路径当中；输出顶点V0到各个顶点的最短路径结束三、详细设计和编码3.1邻接矩阵的定义：我们定义全局变量cost[][],dist[]数组，方便在各子程序中的调用，加快了程序的运行速度。intcost[MAX][MAX];intdist[MAX];intn;cost二维数组用于存放邻接矩阵，每个位置代表的值为图中的权值，其余用无穷大999表示。dist为辅助数组，图中每个顶点对应该数组中的一个元素，这个元素存放当前源点到该顶点的最短路径。此时的路径指示当前结果，并不一定是最终的最短路径。随着集合S的变化，其他顶点不断地加入到集合中，可能以这些新加入的顶点为“桥梁”产生比以前路径更短的路径，dist数组元素的值是动态变化的。n是指图中的顶点数目。3.2结点结构体的定义：struct{intnum;intpnode[MAX];}path[MAX];整型变量num是用来记录求V0到每个顶点的最短路径时所经过的顶点的数目。数组pnode用来存放求V0到每个顶点的最短路径时所经过的顶点，初始为V0。结构体数组path为从V0到各顶点的最短路径。3.3创建带权有向图初始化邻接矩阵cost中的值为无穷大，即任意两个顶点之间不存在路径。首先输入该有向图的顶点数n,然后依次输入各个顶点及边长（输入的顶点的序号应该小于顶点的数目）。输入000结束。定义变量contin，标志输入是否结束。若contin=1，输入继续，若contin=0，输入完成。代码：voidcreatgraph()//创建带权有向图{inti,j,s,e,len,contin=1;printf(\n请输入顶点个数:);scanf(%d,&n);for(i=0;in;i++){for(j=0;jn;j++){cost[i][j]=up;cost[j][i]=up;//初始化所有顶点间的边值均为无穷大}cost[i][i]=0;//每个顶点到自己的边值为0}printf(输入各边，以0，0，0表示结束:\n);i=1;//标志边的数目while(contin==1){printf(\t第%d条边-顶点，顶点，边长:,i);scanf(%d%d%d,&s,&e,&len);if(s==0&&e==0&&len==0)contin=0;elseif(s=0&&sn&&e=0&&en&&len0)//输入的顶点的序号应该小于顶点的数目{cost[s][e]=len;i++;}elseprintf(\t\t边值错误，重复输入!\n);}display(n);//输出所建数组getchar();}3.4邻接矩阵的显示在图的邻接矩阵显示中，分别利用for循环输出了矩阵的行列标，使矩阵很明了。代码：voiddisplay(intn1){inti,j;printf(\n******************************所建图的邻接矩阵**********************************\n);for(i=0;in1;i++)printf(_______%d________,i);//利用for循环输出邻接矩阵的行标printf(\n);for(i=0;in1;i++){printf(%d,i);//利用for循环输出邻接矩阵的列标for(j=0;jn1;j++)printf(\t%3d%d,%d,cost[i][j],i,j);printf(\n);}}3.5Dijkstra求最短路径的实现设图以邻接矩阵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]=1d)利用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]=jf)此时一趟求最短路径完毕，将终点V1添加到路径中。g)循环执行d),e),f)操作，直到全部顶点加入到S中。代码：voidshortdjs()//求最短路径{ints[MAX];intmindis,dis,i,j,v0=0,u=0;//mindis标志图中最短的那一条路径for(i=0;in;i++)//初始化{dist[i]=cost[v0][i];path[i].pnode[0]=v0;path[i].num=0;s[i]=0;}s[v0]=1;for(i=1;in;i++)//将最短路径定点加入到s中{mindis=up;for(j=1;jn;j++)//查找当前的最短路径if(s[j]==0&&dist[j]mindis){u=j;mindis=dist[j];}s[u]=1;for(j=1;jn;j++)//根据j定点调整当前的最短路径if(s[j]==0){dis=dist[u]+cost[u][j];if(dist[j]dis){dist[j]=dis;path[j].num++;path[j].pnode[path[j].num]=u;}}path[i].num++;path[i].pnode[path[i].num]=i;}}3.6最短路径的输出这段函数主要运用for循环，依次输出V0到Vi的最短长度与最短路径。voiddispath()//输出最短路径{inti,j;printf(\n从V0到各顶点的最短路径长度如下：\n);printf((起点-终点)最短长度最短路径\n);printf(---------------------------------\n);for(i=1;in;i++){printf((V0-V%d):,i);if(dist[i]up)printf(\t%d\t,dist[i]);elseprintf(\t∝\t);//显示无穷大for(j=0;jpath