狄斯奎诺算法狄斯奎诺算法
课课课
程程程
设设设
计计计
报
报报
告 告 告
数据结构 课程
狄斯奎诺算法 课程设计名称
沐生 学生姓名
109084255 学号
信息与计算科学102班 专业班级
一、 问题描述和数据结构定义
本次课程设计的题目如下:
选择合适的数据结构表示图,在此基础上实现求解最短路径的狄斯奎诺算法。
:对所设计的图的数据结构提供必要的基本功能。 要求
狄斯奎诺算法意思为,设从顶点v1出发, 找从它到图中所有其它各顶点的最短路径。 狄斯奎诺提出了一个按路径长度递增的顺序产生最短路径的方法。
把...
狄斯奎诺算法
课课课
程程程
设设设
计计计
报
报报
告 告 告
数据结构 课程
狄斯奎诺算法 课程设计名称
沐生 学生姓名
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
#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
本文档为【狄斯奎诺算法】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。