数据结构课程设计报告撰写要求
（一）纸张与页面要求
1．采用国际标准A4型打印纸或复印纸，纵向打印。
2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。
3．图表及图表标题按照模板中的表示书写。
（二）课设报告书的内容应包括以下各个部分：（按照以下顺序装订）
1.封页(见课设模版)
2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。
2.任务书(学生教师均要签字,信息填写完整)
3.目录
4.正文一般应包括以下内容:
（1)题目介绍和功能要求（或描述）
课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述；
（2) 系统功能模块结构图
绘制系统功能结构框图及主要模块的功能说明；
（3) 使用的数据结构的描述: 数据结构设计及用法说明;
（4) 涉及到的函数的描述 ;
（5) 主要算法描述( 程序流程图)
（6) 给出程序测试/运行的结果
设计多组数据加以描述（包括输入数据和输出结果）
（7) 课程设计的总结及体会
（8) 参考文献
格式要求：[1]作者，等. 书名.出版地：出版社，出版年
5.附录：程序清单 (应带有必要的注释)
沈阳航空航天大学
课程设计报告
课程设计名称：数据结构课程设计
课程设计题目：利用弗洛伊德（Floyd)算法求解
最短路径
院（系）：计算机学院
专业：计算机科学与技术(物联网方向)
班级：34010105
学号：
姓名：
指导教师：
说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。
学术诚信声明
本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。
本人签名: 日期：2015 年 1 月 5 日
沈阳航空航天大学课程设计任务书
目录
第一章需求设计
1.1题目介绍 (1)
1.2功能要求 (2)
第二章程序设计 (3)
2.1详细设计 (3)
2.1.1 总体模块图 (3)
2.1.2 函数描述 (4)
2.2主要算法描述 (5)
第三章使用说明 (6)
3.1用法说明 (9)
第四章程序测试 (11)
4.1运行结果 (11)
4.2存在的缺陷 (112)
参考文献 (13)
附录（关键部分程序清单） (14)
第一章需求设计
1.1 题目介绍
给出一张无向图，图上每一个顶点表示一个城市，顶点之间的边表示城市之间存在路径，边上的权值表示城市间的路经长度。利用弗洛伊德（Floyd）算法求解最短路径求解任意两个城市之间的最短路径问题。
将问题分解为三个方面，第一个方面是对于无向图的存储问题，第二个方面是实现弗洛伊德（Floyd）算法求解最短路径，第三个方面是将最短路径输出。首先对于图的建立选择合适的存储结构，考虑到之后要用的弗洛伊德算法所以选择采用邻接矩阵存储无向图。然后采用弗洛伊德算法，该算法又叫插点法。是利用三重循环产生一个存储每个结点最短距离的矩阵，基本思想是设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，p[v][w][u]存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。最后将最短路径的信息输出。
1.2 功能要求
一个无向图用每个顶点代表城市，顶点之间边的权重表示城市之间的路径，将顶点信息和边的信息输入程序，即可得到每两个城市之间的最短路径长度值以及这条路径经过的城市。可以为建址问题提供参考。
设计环境：（1）WINDOWS 7系统
（2）VisualC++开发环境
开发语言：C语言
第二章程序设计2.1 详细设计
2.1.1功能模块图
图2.1功能模块图
2.1.2 函数描述
Find：根据名称得到指定顶点在顶点集合中的下标，利用此函数找到顶点所在位置，进而对无向图赋权值。
Create：创建无向图的邻接矩阵，因为每条边都有权值，创建的是无向网的邻接矩阵，用权值代替1，没有边连接则为无穷。
FLOYD：设置一个n阶矩阵D(k)，D(k)[i][j]表示从i到j的路径长度，k表示运算步骤。用两个顶点之间边的权值作为路径长度，无边连接记做无穷，多次循环，向原路径加入新的顶点，若增加的顶点使得路径比原路径短，则用新路径代替原始路径，将顶点信息存储在另一个三维数组p中，p[v][w][u]存储的是由i到j路径经过的所有顶点。三重循环执行完毕最短路径的信息存储在两个数组中。
主函数：在主函数里定义一个无向图，一个三维矩阵p，二维矩阵D，对各个函数进行调用，实现无向网的建立，运用弗洛伊德算法求解出最短路径，将路径长度以及经过的顶点信息输出。
2.2 主要算法描述
图2.2.1 FLOYD函数
图2.2.2 Find函数
图2.2.3 Main函数
图2.2.4 Create函数
第三章使用说明3.1 用法说明
1.将顶点数和边数输出，中间用空格隔开。
图3.1.1
2.输入顶点信息。
图3.1.2
3.依次输入每条边连接的两个顶点用空格间隔，边的权值。
图3.1.3
4.得到每两个顶点城市间的最短距离以及经过的城市。
图3.1.4
.4
第四章程序测试4.1 运行结果
图4.1
4.2 存在的缺陷
1.无向图的顶点信息只能用一个字符表示。将存储顶点信息的字符型改为字符数组就可以完善该缺陷。
2.将两点的最短路径输出时只能显示经过的顶点有哪些，无法显示真实的路径顺序。
3.输入无向图信息只能用手动输入，无法用文件直接写入。
4.输入不符合要求的数据会使程序自动停止。
沈阳航空航天大学课程设计报告错误！未指定书
签。
参考文献
[1] 张长海.C语言程序设计[M].北京：高等教育出版社，2006
[2]吴启武.C语言课程设计案例精编.北京:清华大学出版社,2011.
[3] 郭翠英.C语言课程设计案例精编.北京:中国水利水电出版社,2004.
[4] 姜灵芝, 余键.C语言课程设计案例精编.北京:清华大学出版社,2008.
[5] 黄明, 梁旭, 万洪莉.C语言课程设计.北京:电子工业出版社,2006
附录（关键部分程序清单）
#include "stdio.h"
#include "stdlib.h"
#define MAX 20
#define INFINITY 9999
typedef bool PathMatrix[MAX][MAX][MAX];
typedef int DistanceMatrix[MAX][MAX];
typedef struct
{
int vexnum,arcnum;
char vexs[MAX];
int arcs[MAX][MAX];
}MGraph;
int Find(char vex, MGraph MG)//根据名称得到指定顶点在顶点集合中的下标vex 表示顶点
{ // return 如果找到则返回下标，否则返回０
int i;
for (i=0;i if (MG.vexs[i] == vex) { return i; } } return 0; } void Create(MGraph &G) { int i,j,k,v1,v2,w; printf("请输入顶点数和边数:"); scanf("%d %d",&G.vexnum,&G.arcnum); getchar(); for(i=0;i { printf("请输入第%d个结点：",i+1); scanf("%c",&G.vexs[i]); getchar(); } for(i=0;i for(j=0;j G.arcs[i][j]=INFINITY; for(k=0;k { char c1,c2; printf("请输入与第%d条边相连的两条边v1 v2:",k+1); scanf("%c",&c1); getchar(); scanf("%c",&c2); printf("请输入该边的权重："); 中南大学 《数据结构》课程设计 题目第9题 Dijkstra算法求最短路径 学生姓名 XXXX 指导教师 XXXX 学院信息科学与工程学院 专业班级 XXXXXXX 完成时间 XXXXXXX 目录 第一章问题分析与任务定义---------------------------------------------------------------------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 :算法的设计思想 本算法采用分支定界算法实现。构造解空间树为：第一个城市为根结点，与第一个城市相邻的城市为根节点的第一层子节点，依此类推；每个父节点的子节点均是和它相邻的城市；并且从第一个根节点到当前节点的路径上不能出现重复的城市。 本算法将具有最佳路线下界的节点作为最有希望的节点来展开解空间树，用优先队列实现。算法的流程如下：从第一个城市出发，找出和它相邻的所有城市，计算它们的路线下界和费用，若路线下界或费用不满足要求，将该节点代表的子树剪去，否则将它们保存到优先队列中，并选择具有最短路线下界的节点作为最有希望的节点，并保证路径上没有回路。当找到一个可行解时，就和以前的可行解比较，选择一个较小的解作为当前的较优解，当优先队列为空时，当前的较优解就是最优解。算法中首先用Dijkstra算法算出所有点到代表乙城市的点的最短距离。算法采用的下界一个是关于路径长度的下界，它的值为从甲城市到当前城市的路线的长度与用Dijkstra算法算出的当前城市到乙城市的最短路线长度的和；另一个是总耗费要小于1500。 伪代码 算法AlgBB() 读文件m1和m2中的数据到矩阵length和cost中 Dijkstra(length) Dijkstra(cost) while true do for i←1 to 50 do //选择和node节点相邻的城市节点 if shortestlength>optimal or mincost>1500 pruning else if i＝50 optimal=min(optimal,tmpopt)//选当前可行解和最优解的 较小值做最优解 else if looped //如果出现回路 pruning //剪枝 else 将城市i插入到优先队列中 end for while true do if 优先队列为空 输出结果 else 取优先队列中的最小节点 if 这个最小节点node的路径下界大于当前的较优解 continue 一、课程设计题目：校园最短路径问题 二、课程设计目的： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所具备的科学工作方法和作风。 三、课程设计要求： 1.设计的题目要求达到一定的工作量（300行以上代码），并具有一定的深度和难度。 2.编写出课程设计报告书，内容不少于10页（代码不算）。 四、需求分析： 1、问题描述 图的最短路径问题是指从指定的某一点v开始，求得从该地点到图中其它各地点的最短路径，并且给出求得的最短路径的长度及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点以及边的增删、边上权值的修改等。 校园最短路径问题中的数据元素有： a) 顶点数 b) 边数 c) 边的长度 2、功能需求 要求完成以下功能： a)输出顶点信息：将校园内各位置输出。 b)输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的 距离输出。 c)修改：修改两个位置（若两个位置之间有直接路径）的距离，并重新输 出每两个位置（若两个位置之间有直接路径）的距离。 d)求最短路径：输出给定两点之间的最短路径的长度及途径的地点或输出 任意一点与其它各点的最短路径。 e)删除：删除任意一条边。 f)插入：插入任意一条边。 3、实现要点 a) 对图的创建采用邻接矩阵的存储结构，而且对图的操作设计成了模板类。 为了便于处理，对于图中的每一个顶点和每一条边都设置了初值。 b) 为了便于访问，用户可以先输出所有的地点和距离。 c) 用户可以随意修改两点之间好的距离。 d) 用户可以增加及删除边。 e) 当用户操作错误时，系统会出现出错提示。 五、概要设计: 题目描述 一个图的存储矩阵如下所示（顶点分别是0、1、2、3、4、5）： 0，12，18，∞，17，∞ 12, 0，10，3，∞，5 18，10，0，∞，21，11 ∞，3，∞，0，∞，8 17，∞，21，∞，0，16 ∞，5，11，8，16，0 试用邻接矩阵存储法和Floyd算法求解任意两个顶点的最短路径。 输入： 输入数据第一行为1个正整：顶点个数n(顶点将分别按0，1，…，n-1进行编号)。后面有n+1行，前n行都有n个整数（第i行第j个数表示顶点i-1和顶点j-1之间的边长，用10000来表示两个顶点之间无边）；第n+1行输入一对顶点x和y 输出： x和y顶点的最短路径长度和最短路径(路径换行输出，只输出顶点编号序列)。 问题分析 题目要求图的存储类型为邻接矩阵，这种存储结构简单易懂，但存储占用较大；求最短路径的算法有Dijkstra算法和SPFA算法，三者相比，在代码的实现上，Floyd编写简单且容易理解，缺点是时间复杂度较高，不适合计算大量的数据。 数据结构及程序 #include for(int i=0;i 摘要 现实生活中许多实际问题的解决依赖于最短路径的应用，其中比较常用的是floyd 算法。通过floyd算法使最短路径问题变得简单化。采用图的邻接矩阵或邻接表实现最短路径问题中图的存储。采用Visual C++6.0的控制台工程和MFC工程分别实现基于floyd算法求最短路径的应用。 关键词：最短路径；floyd算法；邻接矩阵；MFC工程 目录 1需求分析 (1) 2算法基本原理 (1) 2.1邻接矩阵 (1) 2.2弗洛伊德算法 (2) 3类设计 (2) 3.1类的概述 (2) 3.2类的接口设计 (3) 3.3类的实现 (4) 4基于控制台的应用程序 (7) 4.1主函数设计 (7) 4.2运行结果及分析 (8) 5基于MFC的应用程序 (9) 5.1图形界面设计 (9) 5.1程序代码设计 (11) 5.3运行结果及分析 (20) 结论 (21) 参考文献 (22) 1需求分析 Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 假若要在计算机上建立一个交通咨询系统则可以采用图的结构来表示实际的交通网络。这个资讯系统可以回答游客提出的各种问题。例如，一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。假设图中每一站都需要换车，则这个问题反映到图上就是要找一条从顶点A到B所含边的数目最少的路径。我们只需从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径，路径上A与B之间的顶点就是途径中的中转站数。但是这只是一类最简单的图的最短路径的问题。有时对于旅客来说，可能更关心的是节省交通费用；对于司机来说里程和速度则是他们感兴趣的信息。为了在图上标示有关信息可对边赋以权的值，权的值表示两城市间的距离，或图中所需时间，或交通费用等等。此时路径长度的量度就不再是路径上边的数目，而是路径上边的权值之和。边赋以权值之后再结合最短路径算法来解决这些实际问题。Floyd算法是最短路径经典算法中形式较为简单，便于理解的一种。 2算法基本原理 2.1 邻接矩阵 邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（1）对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零（在此仅讨论无向简单图），有向图则不一定如此。 （2）在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。 （3）用邻接矩阵法表示图共需要个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 数据结构 设计说明书 单源点最短路径算法的实现 学生姓名王文刚 学号1418064056 班级网络1402 成绩 指导教师 数学与计算机科学学院 年月日 课程设计任务书 20 —20 学年第学期 课程设计名称：数据结构课程设计 课程设计题目：单源点最短路径算法的实现 完成期限：自年月日至年月日共 2 周设计内容： 1.任务说明 2.要求 3.参考资料 指导教师：教研室负责人： 课程设计评阅 摘要 设计了一求解最短路径的方法，该方法具有在输入的途中查找两个顶点之间的最短路径的功能。本方法采用VC++作为软件开发环境，采用Dijkstar函数来求取顶点之间的最短路径。，用户可以自己输入各个地点及其之间的距离，便于用户在不同情况下均可使用。 关键词：最短路径；Dijkstar；无向图; 目录 目录 1课题描述 (2) 2 需求分析 (3) 3概要设计 (4) 3.1 存储结构 (4) 3.2 算法描述 (5) 4详细设计 (6) 4.1 功能模块图 (6) 4.2 主函数 (6) 4.3 pd函数 (7) 4.4 CreateMGraph函数 (8) 4.5Dijkstar函数 (9) 5程序编码 (11) 6程序的调试与测试 (15) 8总结 (16) 参考文献 (17) 1.目录中可以只有一级标题 2.页码右侧对齐页边距 3.本页不需要页码 4.以上内容仅作参考，具体章节由课程设计类型确定 1课题描述 随着交通的发展，人民生活水平的提高。出门旅行变的越来越频繁，而且供暖也成为冬天不可或缺的内容。为了节约时间和金钱，所以人们都希望找到旅行目的地的最短路径和架设暖气的最短路径。那么如何找到最短路径呢？由于路径较多，手工计算比较麻烦，而且容易出错，因此人们用计算机语言代替手工计算求最短路径。而在计算机语言中迪杰斯特拉算法比较常见，简洁，故人们常借助计算机程序迪杰斯特拉算法求最短路径。这样可以广泛提高效率，容易理解。 数据结构与算法课程实验报告实验四：图的相关算法应用 姓名：王连平 班级：09信科2班 学号：I09630221 实验四图的相关算法应用 一、实验内容 求有向网络中任意两点之间的最短路。 二、实验目的 掌握图和网络的定义，掌握图的邻接矩阵、邻接表和十字链表等存储表示。掌握图的深度和广度遍历算法，掌握求网络的最短路的标号法和floyd算法。 三、问题描述 对于下面一张若干个城市以及城市间距离的地图，从地图中所有可能的路径中求出任意两个城市间的最短距离及路径，给出任意两个城市间的最短距离值及途径的各个城市。 四、问题的实现 4.1数据结构的抽象数据类型定义和说明 1） typedef struct ArcCell{//储存弧信息 int Distance; ArcCell *info;//此项用来保存弧信息，，在本实验中没有相关信息要保存 }ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct{//储存顶点信息 string vexs[ MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵 int vexnum , arcnum;//图的当前顶点数和弧数 }MGraph; 顶点信息和弧信息都是用来建立一个有向网G 2） d[v][w];//G中各对顶点的带权长度 若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点 4.2主要的实现思路 首先通过一个函数（CreateDN）建立图的邻接矩阵储存方式,一次输入某条弧的起点，终点，和权值。通过调用Locate函数来找到该弧在邻接矩阵中的相应位置。 其次运用弗洛伊德算法来求各定点的最短路劲，具体思路为：如果从v到w有弧，则存在一条长度为arcs[v][w]的路径，该路径不一定是最短路径。考虑路径（v,u,w）是否存在，若存在，比较（v,w）和（v,u,w）的长度，取较短者为从v到w的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从v到w的最短路径。按此方法，可以同时求得任意两点间的最短路径。 五、主要源程序代码（包含程序备注） #include 《数据结构课程设计》最短路径问题实验报告 目录 一、概述 0 二、系统分析 0 三、概要设计 (1) 四、详细设计 (5) 4.1建立图的存储结构 (5) 4.2单源最短路径 (6) 4.3任意一对顶点之间的最短路径 (7) 五、运行与测试 (8) 参考文献 (11) 附录 (12) 交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 三、概要设计 可以将该系统大致分为三个部分： ①建立交通网络图的存储结构； ②解决单源最短路径问题； ③实现两个城市顶点之间的最短路径问题。 迪杰斯特拉算法流图： 最短路径问题的算法分析及建模案例 最短路径问题的算法分析及建模案例 一.摘要 (3) 二.网络最短路径问题的基础知识 (5) 2.1有向图 (7) 2.2连通性................... 错误！未定义书签。 2.3割集....................... 错误！未定义书签。 2.4最短路问题 (8) 三．最短路径的算法研究.. 错误！未定义书签。 3.1最短路问题的提出 (9) 3.2 Bellman最短路方程错误！未定义书签。 3.3 Bellman-Ford算法的基本思想错误！未定义书签 3.4 Bellman-Ford算法的步骤错误！未定义书签。 3.5实例....................... 错误！未定义书签。 3.6 Bellman-FORD算法的建模应用举例错误！未定义 3.7 Dijkstra算法的基本思想 (9) 3.8 Dijkstra算法的理论依据 (9) 3.9 Dijkstra算法的计算步骤 (9) 3.10 Dijstre算法的建模应用举例 (10) 3.11 两种算法的分析错误！未定义书签。 1.Diklstra算法和Bellman-Ford算法 思想有很大的区别错误！未定义书签。 Bellman-Ford算法在求解过程中，每 次循环都要修改所有顶点的权值，也就 是说源点到各顶点最短路径长度一直 要到Bellman-Ford算法结束才确定下 来。...................... 错误！未定义书签。 2.Diklstra算法和Bellman-Ford算法 的限制.................. 错误！未定义书签。 3.Bellman-Ford算法的另外一种理解错误！未定 4.Bellman-Ford算法的改进错误！未定义书签。 摘要 近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径 问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等 诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的 一个典型例子。 由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究， 使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最 短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题 青岛理工大学琴岛学院 设计报告 课题名称：求解最优交通路径 学院：计算机工程系 专业班级：计算机科学与技术 学号：####### 学生：** 指导教师：** 青岛理工大学琴岛学院教务处 2011 年 7 月 7日 图1 B.具体功能实现及相应的弗洛伊德算法 首先,建立查询信息对话框，使用户能够录入需要查询的城市代号，并显示路径长度及最短路径沿途经过的城市。并相应地添加如下变量int m_v0;int m_v1;int m_lj;CString m_zd; 具体代码如下： #define MAXV 25 //最大顶点个数 #define INF 32767 //用32767表示∞ //以下定义邻接矩阵类型 typedef struct { int no; //顶点编号 char name[10]; //顶点名称 } VertexType; //顶点类型 typedef struct //图的定义 { int edges[MAXV][MAXV]; //邻接矩阵 int vexnum,arcnum; //顶点数，弧数 VertexType vexs[MAXV]; //存放顶点信息 } MGraph; //图的邻接矩阵类型 1.通过函数CreatUDN()存放城市路径信息，输入顶点之间的路径长度，创建带权图的邻接矩阵。 void CTDialog::CreatUDN() { MGraph *g=(MGraph*)malloc(sizeof(MGraph)); int i,j; for(i=0;i 数据结构课程设计题目 2012-1 1、医务室模拟。（5人） 问题描述：假设只有一位医生，在一段时间内随机地来几位病人；假设病人到达的时间间隔为0~14分钟之间的某个随机值，每个病人所需处理时间为1~9分钟之间的某个随机值。试用队列结构进行模拟。 实现要求：要求输出医生的总等待时间和病人的平均等待时间。 程序设计思路：计算机模拟事件处理时，程序按模拟环境中的事件出现顺序逐一处理，在本程序中体现为医生逐个为到达病人看病。当一个病人就诊完毕而下一位还未到达时，时间立即推进为下一位病人服务，中间时间为医生空闲时间。当一个病人还未结束之前，另有一位病人到达，则这些病人应依次排队，等候就诊。 2、招聘模拟（5人） 问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号（0，1，2，…，m-1）和计划招聘人数，参加招聘的人数有n个（编号为0，1，2，。。。，n-1）。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司的录取原则是：从高分到低分依次对每位应聘者按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队，并按其志愿考虑录取。 程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满，或已对全部应聘者都做了录用处理。 实现要求：要求程序输出每个工种录用者的信息（编号、成绩），以及落选者的信息（编号、成绩）。 3、组织机构问题（5人） 问题描述：以物资学院为例，实现对我校组织结构的管理。要求把我校的组织结构以树型结构存储，实现要求： （1）树中每个结点保存部门名称； （2）假定处级部门（含院系）在树中第二层，科级部门在第三层（即最后一层），软件应该能计算出处级部门有几个，有哪几个？ （3）软件可以查询某部门下面的具体编制？ 4、最少换车次数问题（5人） 问题描述：设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车站都是单向的，这n个车站被顺序编号为0~n-1。编程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。 实现要求：求得从站0出发乘公交车至站n-1的最少换车次数。 设计思路：利用输入信息构建一张有向图G（邻接矩阵存储），有向图的顶点表示车站，若某条公交线路经i站能到达j站，就在图G中存在一条有向边 课程设计任务书 目录 第1章概要设计 (1) 1.1题目的内容与要求 (1) 1.2总体结构 (1) 第2章详细设计 (2) 2.1主模块 (2) 2.2构建城市无向图 (3) 2.3添加城市 (4) 2.4修改城市距离 (5) 2.5求最短路径 (6) 第3章调试分析 (7) 3.1调试初期 (7) 3.2调试中期 (7) 3.3调试末期 (7) 第4章测试及运行结果 (7) 附页（程序清单） (10) 第1章概要设计 1.1题目的内容与要求 内容：给出一张无向图，图上的每个顶点表示一个城市，顶点间的边表示城市间存在路径，边上的权值表示城市间的距离。试编写程序求解从某一个城市出发到达任意其他任意城市的最短路径问题。 要求： 1)能够提供简单友好的用户操作界面，可以输入城市的基本信息，包括城市名 称，城市编号等； 2)利用矩阵保存城市间的距离； 3)利用Floyd算法求最短路径； 4)独立完成系统的设计，编码和调试； 5)系统利用C语言完成； 6)按照课程设计规范书写课程设计报告。 1.2总体结构 本程序主要分为四个模块（功能模块见图1.1）：主模块对整个程序起一主导作用，开始构建一城市无向图，对其进行添加城市顶点，以及对原来的距离数据进行修改，整体构建结束可以实现求一城市到其他城市的最短路径问题。 图1.1 功能模块图 第2章详细设计 2.1主模块 用户根据屏幕上显示的操作提示输入要进行操作的模块，通过调用相对应的模块程序，达到用户所想进行操作。程序的总框架大致分为四个模块：1.建立城市无向图2.添加城市模块3.修改城市距离4.求最短路径。具体实现过程见2.2：建立城市无向图2.3：添加城市2.4：修改城市距离2.5：求最短路径。流程图中通过输入n，由n的值来选择调用相对应子函数，实现所选择的功能，调用完后可以返回调用主函数进行下一次选择，从而实现反复调用子函数而实现四个模块的功能等。 图2.1 主模块流程图 浙江大学城市学院实验报告 课程名称数据结构与算法 实验项目名称实验八图的最短路径问题 实验成绩指导老师（签名）日期 一.实验目的和要求 1.掌握图的最短路径概念。 2.理解并能实现求最短路径的DijKstra算法（用邻接矩阵表示图）。 二. 实验内容 1、编写用邻接矩阵表示有向带权图时图的基本操作的实现函数，基本操作包括： ①初始化邻接矩阵表示的有向带权图void InitMatrix(adjmatrix G); ②建立邻接矩阵表示的有向带权图void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; ③输出邻接矩阵表示的有向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。 把邻接矩阵的结构定义以及这些基本操作函数存放在头文件Graph2.h中。2、编写求最短路径的DijKstra算法函数void Dijkstra( adjmatrix GA, int dist[], edgenode *path[], int i, int n) ，该算法求从顶点i到其余顶点的最短路径与最短路径长度，并分别存于数组path 和dist 中。编写打印输出从源点到每个顶点的最短路径及长度的函数void PrintPath(int dist[], edgenode *path[], int n)。 3、编写测试程序（即主函数），首先建立并输出有向带权图，然后计算并输出从某顶点v0到其余各顶点的最短路径。 要求：把指针数组的基类型结构定义edgenode、求最短路径的DijKstra算法函数、打印输出最短路径及长度的函数PrintPath以及主函数存放在文件 test9_2.cpp中。 测试数据如下： 东华大学计算机学院离散数学 实验五：最短路径 实验所属系列：离散数学课后实验 实验对象：本科 相关课程及专业：离散数学，计算机专业 实验类型：课后实验 实验时数（学分）：4学时 实验目的 学习图的最短路径算法的实现。 实验内容与要求 根据输入的图形（实验四），输入起点和终点，求出最短路径和最短路径的长度。 实验的软硬件环境 PC机一台，装有VC++6.0或其它C语言集成开发环境。 实验准备 熟悉最短路径算法。 实验步骤 1．编写一段代码，接收键盘的输入定点的数量，并以输入的整数对作为边来建立图形的邻接矩阵（无向权重图）。 例如：5，6，12 表示定点5和定点6间有边，边的权重为12。 2 打印出邻接矩阵。 3．输入起点和终点。 4、打印最短路径和最短路径的长 #include 《数据结构课程设计》报告 最短路径—拯救007 专业 xxxxxx 学生姓名 xxxx 班级 xxxx 学号 xxxx 指导教师 xxxxx 完成日期 xxxxxx 目录 一、简介 (3) 二、算法说明 (4) 三、测试结果 (7) 参考文献 (14) 一、简介 最短路径是，在一个图中，若从一个顶点到另一个顶点存在着一条路径（这里只讨论无回路的简单路径），则称该条路径长度为为该路径上所有经过的边的数目，它也等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条路径，在每条路径上所经过的边数可能不同，把路径长度最短（经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短距离。这是对无权图而言的，若图是帯权图，则把从一个顶点vi到vj的一条路径上所有经过边的权值之和定义为该路径的带权路径长度。把带权路径长度最短的那条路径称为该有权图的最短路径，其路径长度称为最短距离。 Dijksra算法：如何求解从一个顶点到其余每个顶点的最短路径呢？狄克斯特拉于1959年提出了解决此问题的一种按路径长度的递增次序产生最短路径的算法。基本思想是，从图中给定源点到其他各个顶点之间客观上应个存在一条最短路径，在这组最短路径中，按其长度的递增次序求出到不同顶点的最短路径和路径长度。 图是一种较线性结构和树形结构更为复杂的非线性数据结构，这种复杂性主要来自数据元素之间的复杂关系。在图结构中，任何两个数据元素之间都可能存在关系，一般用顶点表示数据元素，而用顶点之间的连线表示数据元素之间的关系。图的二元组定义为：G=(V,E)。其中V是非空的顶点集合，E是V上的二元关系集合。 题目内容： 看过007系列的电影的人们一定很熟悉Jams Bond这个世界上最著名的特工了。在电影“Live And Let Die”中Jams Bond被一组毒品贩子抓住并且关到湖中心的一个小岛上，而湖中有很多凶猛的鳄鱼。这时Jams Bond做出了一个最惊心动魄的事情来逃脱——他跳到了最近的鳄鱼的头上，在鳄鱼还没有反映过来的时候，他有跳到另一支鳄鱼的头上.。。。。。。最后他终于安全地跳到了湖岸上。 假设湖是100*100的正方形，设湖的中心在（0，0），湖的东北角的坐标是（50，50）。湖中心的圆环小岛的圆心在（0，0），直径是15.。一些凶残的鳄鱼分布在湖中不同的位置。现已知的湖中的鳄鱼的位置和Jams Bond可以跳的最大距离，请你告诉Jams Bondyitiao 最短的到达湖边的路径。他逃出去的路径长度等于他跳的次数。 实验报告六月 18 2015 姓名：陈斌学号：E 专业：13计算机科学与技术数据结构第八次实验 学号E专业计算机科学与技术姓名陈斌 实验日期教师签字成绩 实验报告 【实验名称】最小生成树和最短路径 【实验目的】 (1)掌握最小生成树以及最短路径的相关概念； (2)掌握Prim算法和Kruskal算法； (3)掌握Dijkstra算法 【实验内容】 采用普里姆算法求最小生成树 (1)编写一个算法，对于教材图(a)所示的无向带权图G采用普里姆算法输出从顶点 V1出发的最小生成树。图的存储结构自选。 (2)对于上图，采用克鲁斯卡尔算法输出该图的最小生成树。（提示：a.先对边按 权值从小到大排序，得有序边集E；为所有顶点辅设一个数组Vset，标记各顶点所处的连通分量，初始时各不相同。b. 依次从E中取出一条边(i,j)，检查顶点i和j是否属于同一连通分量，如是，则重取下一条边；否则，该边即为生成树的一条边，输出该边，同时将所有与j处于同一连通分量的顶点的Vset 值都修改为与i的相同。c.重复b步直至输出n-1条边。） 源代码： : #include<> #include<> #include<> dj=INFINITY; /* 网 */ } printf("请输入%d条边的顶点1 顶点2 权值(用空格隔开): \n",; for(k=0;k<;++k) { scanf("%s%s%d%*c",va,vb,&w); /* %*c吃掉回车符 */ i=LocateVex(G,va); j=LocateVex(G,vb); [i][j].adj=[j][i].adj=w; /* 无向 */ } =AN; return OK; } typedef struct { /* 记录从顶点集U到V-U的代价最小的边的辅助数组定义 */ VertexType adjvex; VRType lowcost; }minside[MAX_VERTEX_NUM]; int minimum(minside SZ,MGraph G) { /* 求的最小正值 */ int i=0,j,k,min; while(!SZ[i].lowcost) i++; min=SZ[i].lowcost; /* 第一个不为0的值 */ k=i; for(j=i+1;j<;j++) if(SZ[j].lowcost>0) 数据结构课程设计报告撰写要求 （一）纸张与页面要求 1．采用国际标准A4型打印纸或复印纸，纵向打印。 2．封页和页面按照下面模板书写（正文为：小四宋体1.5倍行距）。 3．图表及图表标题按照模板中的表示书写。 （二）课设报告书的内容应包括以下各个部分：（按照以下顺序装订） 1.封页(见课设模版) 2、学术诚信声明，所有学生必须本人签字，否则教师拒绝给予成绩。 2.任务书(学生教师均要签字,信息填写完整) 3.目录 4.正文一般应包括以下内容: （1)题目介绍和功能要求（或描述） 课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述； （2) 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明； （3) 使用的数据结构的描述: 数据结构设计及用法说明; （4) 涉及到的函数的描述 ; （5) 主要算法描述( 程序流程图) （6) 给出程序测试/运行的结果 设计多组数据加以描述（包括输入数据和输出结果） （7) 课程设计的总结及体会 （8) 参考文献 格式要求：[1]作者，等. 书名.出版地：出版社，出版年 5.附录：程序清单 (应带有必要的注释) 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：利用弗洛伊德（Floyd)算法求解 最短路径 院（系）：计算机学院 专业：计算机科学与技术(物联网方向) 班级：34010105 学号： 姓名： 指导教师： 说明：结论（优秀、良好、中等、及格、不及格）作为相关教环节考核必要依据；格式不符合要求；数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。数据结构课程设计报告Dijkstra算法求最短路径
最短路径流程图及算法详解
数据结构,课程设计,校园最短路径问题
数据结构最短路径
基于Floyd算法的最短路径问题的求解c++
数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构最短路径
实验四-图的最短路径(弗洛伊德算法实现)
《数据结构课程设计》最短路径问题实验报告
最短路径问题的算法分析及建模案例
数据结构课程设计报告_最短路径C++
数据结构课程设计题目(最终版)-2011
弗洛伊德算法求解最短路径
【数据结构算法】实验8 图的最短路径问题(附源代码)
最短路径算法实验报告
课程设计--最短路径：拯救007
最小生成树和最短路径数据结构实验
数据结构课程设计-Floyd算法求解最短路径
相关主题
文本预览