狄斯奎诺算法

狄斯奎诺算法 课课课 程程程 设设设 计计计 报 报报 告 告 告 数据结构 课程 狄斯奎诺算法 课程名称 沐生 学生姓名 109084255 学号 信息与计算科学102班 专业班级 一、 问题描述和数据结构定义 本次课程设计的题目如下: 选择合适的数据结构表示图，在此基础上实现求解最短路径的狄斯奎诺算法。 :对所设计的图的数据结构提供必要的基本功能。 要求 狄斯奎诺算法意思为，设从顶点v1出发, 找从它到图中所有其它各顶点的最短路径。 狄斯奎诺提出了一个按路径长度递增的顺序产生最短路径的方法。 把图中顶点集合分成两组，第一组为集合S，存放已求出其最短路径的顶点，第二组为尚未确定最短路径的顶点集合是V-S(用U表示)，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个把U中的顶点加到S中，直到S中包含全部顶点，而U为空。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。 算法:我们可以将图中的顶点分为两组: S ——已求出的最短路径的终点集合(开始为{v0}) V-S ——尚未求出最短路径的顶点集合(开始为V,{v0}的全部结点)。 按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中。 引进辅助向量dist[ ] ，它的每一个分量dist[i]表示已经找到的且从开始点v0到每一个终点vi 的当前最短路径的长度。 它的初态为:如果从v0到vi 有弧，则dist[i] 为弧的权值;否则，dist[i] 为? ，即为MAX。 定义数组P[i][j]用来存放一个有向网产生的邻接矩阵。Vi->Vj之间有弧的时候，P[i][j]=1。Vi->Vj之间不存在弧的时候，P[i][j]=0。于是产生一个n*n的方阵。方便直观的让读者判断顶点i 和顶点j 是否有弧相连。 找下一条长度次短的路径。假设该次短路径的终点是vk，则这条路径可能是(v0 , vk) 或者是(v0 , vj , vk)。 二、设计思路 用一维数组来存储顶点的信息，二维数组来存储边的信息，通过输入顶点和边的信息，最终将最短路径的结果保存在Dist[]数组中输出。 开始 初始化图的顶点和边的信息 调用ShortestPath_DIJ函数进行计 算最短路径 dist[i]= g.arcs[v0][vi] 比较dist[i]，选出最小值，为Vk 使得dist[k] = Min{dist[i]}，将vk并入S集 dist[k]+g.arcs[k][i]与的大小，若dist[k]+g.arcs[k][i] #include #include #define MAX_NAME 10 #define MAX_V_N 26 #define MAX 32768 typedef char VertexData[MAX_NAME]; typedef int AdjMatrix[MAX_V_N][MAX_V_N];//邻接距阵 struct MGraph//定义网 { VertexData vexs[MAX_V_N]; AdjMatrix arcs; int vexnum,arcnum; }; int LocateVex(MGraph G,VertexData u)//定位 { int i; for(i=0;i