数据结构课程设计最短路径问题实验报告.doc
文本预览下载声明
目 录
TOC \o 1-3 \h \u HYPERLINK \l _Toc24866 一、概述 PAGEREF _Toc24866 1
HYPERLINK \l _Toc3421 二、系统分析 PAGEREF _Toc3421 1
HYPERLINK \l _Toc19074 三、概要设计 PAGEREF _Toc19074 2
HYPERLINK \l _Toc8261 四、详细设计 PAGEREF _Toc8261 5
HYPERLINK \l _Toc16216 4.1建立图的存储结构 PAGEREF _Toc16216 5
HYPERLINK \l _Toc26937 4.2单源最短路径 PAGEREF _Toc26937 6
HYPERLINK \l _Toc23990 4.3任意一对顶点之间的最短路径 PAGEREF _Toc23990 7
HYPERLINK \l _Toc21396 五、运行与测试 PAGEREF _Toc21396 8
HYPERLINK \l _Toc15084 参考文献 PAGEREF _Toc15084 11
HYPERLINK \l _Toc8504 附录 PAGEREF _Toc8504 12
交通咨询系统设计(最短路径问题)
一、概述
在交通网络日益发达的今天,针对人们关心的各种问题,利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系,图中顶点表示城市,边表示各个城市之间的交通关系,所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题,例如:如何选择一条路径使得从A城到B城途中中转次数最少;如何选择一条路径使得从A城到B城里程最短;如何选择一条路径使得从A城到B城花费最低等等的一系列问题。
二、系统分析
设计一个交通咨询系统,能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求,可输入城市间的路程、所需时间或是所需费用等信息。
针对最短路径问题,在本系统中采用图的相关知识,以解决在实际情况中的最短路径问题,本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题,这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单,方便使用者的使用。
三、概要设计
可以将该系统大致分为三个部分:
建立交通网络图的存储结构;
解决单源最短路径问题;
实现两个城市顶点之间的最短路径问题。
交通咨询系统
交通咨询系统
迪杰斯特拉算法(单源最短路径)费洛依德算法(任意顶点对间最短路径)建立图的存储结构义
迪杰斯特拉算法(单源最短路径)
费洛依德算法(任意顶点对间最短路径)
建立图的存储结构义
迪杰斯特拉算法流图:
弗洛伊德算法流图:
四、详细设计
4.1建立图的存储结构
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下定义的n阶方阵。
注:一个图的邻接矩阵表示是唯一的!其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息(下标为i的元素存储顶点的信息)。
邻接矩阵的存储结构:
#define MVNum 100 //最大顶点数
typedef struct
{
VertexType vexs[MVNum];//顶点数组,类型假定为char型
Adjmatrix arcs[MVNum][MVNum];//邻接矩阵,假定为int型
}MGraph;
注:由于有向图的邻接矩阵是不对称的,故程序运行时只需要输入所有有向边及其权值即可。
4.2单源最短路径
单源最短路径问题:已知有向图(带权),期望找出从某个源点S∈V到G中其余各顶点的最短路径。
迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。
算法思想:设有向图G=(V,E),其中V={1,2,……n},cost是表示G的邻接矩阵,
cost[i][j]表示有向边i,j的权。若不存在有向边i,j,则cost[i][j] 的权为无穷大(这里取值为32767)。设S是一个集合,集合中一个元素表示一个顶点,从源点到这些顶点的最短距离已经求出。设顶点V1为源点,集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离,其初值为dist[i]= cost[i][j],i=2,……n。从S之外的顶点集合V-S中选出一个顶点w,使dist[w] 的值最小。于是从源点到达w只通过S中的顶点,把w加入集合S中,调整dist中记录的从源点到V-S中每个顶
显示全部