数据结构课程设计最短路径问题实验报告.docx

生产计划与控制课程设计轴承生产.docx

生产计划与控制课程设计轴承生产本科课程设计说明书生产计划与控制设计 教 学 院: 机电工程学院系 别:工业工程系学生学号:学生姓名:专业班级:指导教师:职 称:起止日期:学 院 名 称目录1企业简介21.1企业自然情况及设备21.2产品简介,

《数据结构课程设计最短路径问题实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计最短路径问题实验报告.docx（20页珍藏版）》请在上搜索。

1、数据结构课程设计最短路径问题实验报告目 录 一、概述1二、系统分析1三、概要设计2四、详细设计54.1建立图的存储结构54.2单源最短路径64.3任意一对顶点之间的最短路径7五、运行与测试8参考文献11附录12交通咨询系统设计（最短路径问题）一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择

2、一条路径使得从A城到B城花费最低等等的一系列问题。二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。三、概要设计可以将该系统大致分为三个部分： 建立交通网络图的存储结构； 解决单源最短路

3、径问题； 实现两个城市顶点之间的最短路径问题。交通咨询系统迪杰斯特拉算法（单源最短路径）费洛依德算法（任意顶点对间最短路径）建立图的存储结构义迪杰斯特拉算法流图：弗洛伊德算法流图：四、详细设计 4.1建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点的信息）。邻接矩阵的存储结构：#define MVNum 100 /最大顶点数

4、typedef struct VertexType vexsMVNum;/顶点数组，类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵，假定为int型MGraph;注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。4.2单源最短路径单源最短路径问题：已知有向图(带权)，期望找出从某个源点SV到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图G=(V,E)，其中V=1,2，n，cost是表示G的邻接矩阵， costij表示有向边的权。若不存在有向边，则costij 的权为无穷大（这

5、里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离，其初值为disti= costij，i=2，n。从S之外的顶点集合V-S中选出一个顶点w，使distw 的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的distv和distw+costwv中选择较小的值作为新的distv。重复上述过程，直到S中包含V中其余顶点的最短路径。 最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。 4.3任意一对顶点之间的最短路径 任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(VW)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。