logo资料库

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

发布时间：2022-06-03 发布人：admin 分类：说明书 资料大小：0.18M 资料格式：doc 举报 版权申诉
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
资料共17页，剩余部分请下载后查看
    中南大学 《数据结构》课程设计 题 目 第 9 题 Dijkstra 算法求最短路径 学生姓名 指导教师 学 院 专业班级 完成时间 XXXX XXXX 信息科学与工程学院 XXXXXXX XXXXXXX 1
    目录 第一章 问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章 数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章 详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra 算法实现最短路径--------------------------------------------------------------10 第四章 上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章 测试结果-----------------------------------------------------------------------------------12 第六章 学习心得体会-----------------------------------------------------------------------------12 第七章 参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12 2
    第一章 问题分析与任务定义 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 找到的最短路径如何输出。 3
    第二章 数据结构的选择和概要设计 1.数据结构的选择： 在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复 杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方 面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数 可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多 存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来 很大的困难。 在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中 两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的， 采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素， 时间复杂度为 O（n2）,这对于顶点很多而边较少的图（稀疏图）是非常不合 算的。 以邻接矩阵存储有向图。 2.概要设计 2.1 对于最短路径问题： 最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径 是： （1）从某源点到其余各顶点之间的最短路径。 （2）每一段顶点之间的最短路径 在这里我们解决第一类问题。 2.2 Dijkstra 算法用于求最短路径： Dijkstra 算法是按路径长度递增的次序逐步产生源点到其他顶点间 的最短路径。算法建立一个顶点集合 S，初始时该集合只有源点 V0，然后 逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合 S 中，算法结束。 2..3 Dijkstra 算法思想 设 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]< distance[i]) { distance[i]= 4
    distance[j] ]+cost[i,j] } 5)重复操作 2）、3）、4），直到全部顶点加入到 S 中。 2.4 实现流程 在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入 图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。 当建立图之后，对图进行遍历才能使用 Dijkstra 算法求出最短路径；在 完成了图的建立之后，用 Dijkstra 算法的思想，从单源点开始，求出到 各个顶点的最短路径，并能够实现显示功能。 程序流程图： 开始 输入顶点边个数 输入顶点名称 输入每条边的信息 创建图 返回每个结点 的位置 Dijkstra 算法的实现 D[w]
    (1) 输入顶点个数 n，边的条数，初始化邻接矩阵。 (2)初始化所每条边的权值与 D[h]中 (3) ① 找出 v0 到图中其他各点的最小值 ② 经过改最小值的点到除它外其他各点的最小值 ③ 直到 s 中的所有值全部被处理过， (4) 输出各最短路径的长度 D[w] 算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。 第三章 详细设计和编码 3.1 框架的建立 typedef char VertexType;//定义图的顶点为字符型 typedef int VRType; //顶点关系类型 typedef int InfoType;//该弧相关信息 typedef struct ArcCell{ VRType adj;//权值 InfoType *info;//弧相关信息的指针 }ArcCell; typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//一维数组，存储顶点 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 ：二维数组， 存储边和弧 int vexnum,arcnum;//图的当前顶点数和弧数 }MGrph; //邻接矩阵表示的图 3.1.1 顶点的定义 typedef char VertexType;//定义图的顶点为字符型 顶点的 最大个数 25 3.1.2ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];二维数组用于存放邻 接矩阵，每个位置代表的值为图中的权值，其余用无穷大 3000 表示。 3.2 点结构体的定义 确定位置函数 /* int LocateVex(MGrph *G,VertexType v) { int j,b; */ 6
    for(b=0;bvexnum;b++)//在所有顶点中寻找 if(G->vexs[b]==v)//找到所找的顶点在 b 位置 { j=b; break; }//if return(j); } //LocateVex 3.3 创立带权值有向图 首先输入该有向图的顶点数 n,然后依次输入各个顶点及边长（输入的顶点的序 号应该小于顶点的数目）。 /* void Creat_YG(MGrph *G) { 有向图的建立 */ int i,k,j,n; VertexType v1,v2; int w=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 的位置 7
    G->arcs[i][j].adj=n;//边的权值赋为 1，如需要权值操作则相应修改一下即可 G->arcs[i][j].info=NULL;//如需要有相关信息则相对应输入，在这里我设置为空 }//第二个 for getchar(); } //Creat_YG void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,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].adjarcs[j][k].adj); else printf("\t 3000"); //无权值的直接输出最大值 } } 3.4 邻接矩阵的显示 在图的邻接矩阵显示中，分别利用 for 循环输出了矩阵的行列标，使矩阵很明了。 void juzhen(MGrph *G){//用矩阵来存储并显示出结果 int i,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++) { 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    行业

    共收录7266份资料，累计15个分类，关注成员有19位，主要包括：物流,旅游,餐饮零售,网络游戏,咨询,金融,电子政务,外包,教育,制造,医疗,嵌入式,互联网,交通,电信

    热门标签

    物流 旅游 餐饮零售 网络游戏 咨询 金融 电子政务 外包 教育 制造 医疗 嵌入式 互联网 交通 电信

    最新资料