数据结构 实验报告五 最短路径

数据结构 实验报告五 最短路径

实验课程名称 数据结构课程设计 专 业 班 级

学 生 姓 名 学 号 指 导 教 师

2012至 2013学年第 一 学期第 1 至 9 周

目录

一、概述： ..................................................................................................................... 3 1.1 问题描述............................................................................................................... 3 1.2 系统实现的目标.................................................................................................... 3 1.3 系统实现方案 ....................................................................................................... 3 二、系统分析： .............................................................................................................. 4 2.1设计思想................................................................................................................ 4 2.2设计要求................................................................................................................ 4 2.3需求分析................................................................................................................ 4 2.4 算法描述 ............................................................................................................. 5 三、概要设计： .............................................................................................................. 7 3.1 程序流程图 ........................................................................................................... 8 四、详细设计： .............................................................................................................. 9 4.1建立图的存储结构 ................................................................................................. 9 4.2单源最短路径 ........................................................................................................ 9 4.3任意一对顶点间最短路径 .................................................................................... 10 4.4 建立有向图的存储结构....................................................................................... 11 4.5迪杰斯特拉算法................................................................................................... 11 4.6弗洛伊德算法 ...................................................................................................... 12 4.7 运行主控程序 ..................................................................................................... 13 五、运行与测试： ........................................................................................................ 14 六、：总结与心得 ........................................................................................................ 16 附录：程序代码 ........................................................................................................ 16

一、概述：

1.1 问题描述

在交通网络非常发达,交通工具和交通方式不断更新的今天,人们在出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需要的时间等问题也感兴趣。对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中的顶点表示城市，边表示城市之间的交通关系。这个交通系统可以回答出行旅客提出的各种路径选择问题。例如，问题之一：“一位旅客要从A城到B城，他希望选择一条途中中转次数最少的路线。”假设图中每一站都需要换车，那么这个问题反映到图上就是要找一条从顶点A到顶点B的所含边数目最少的路径。我们只需要从顶点A出发对图作广度优先搜索，一旦遇到顶点B就终止。由此所得广度优先生成树上，从根顶点A到顶点B的路径就是中转次数最少的路径。路径上A与B之间的顶点就是路径的中转站，但这只是一类最简单的图的最短路径问题。系统还可以回答诸如此类的等等的路径选择问题。

1.2 系统实现的目标

通过进行课程设计，了解并初步掌握设计、实现较大系统的完整过程，包括：系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。

1.3 系统实现方案

首先确定系统要实现怎样的目的，实现这些目的需要先实现哪些程序，这就是核心部分，划分出模块并写出其源代码，此程序大致分了六大模块，由一个主函数组和五个自定义函数组成，而后是上机调试，将几大模块组成一个协调完整的能实现其功能的程序，最后提交设计报告

二、系统分析：

2.1设计思想

用邻接矩阵来存储交通网络图的信息，运用迪杰斯特拉算法实现图上单源最短路径问题，然后运用费洛伊德算法实现图中任意一对顶点间最短路径问题，这样就会实现旅客所要咨询的问题。

2.2设计要求

该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的 最短路径问题。故设计要分成三部分，一是建立交通网络图的存储结构；二是解决单源路径问题；最后再实现两个城市之间的最短路径问题。

设计要求：

1. 建立交通网络网的存储结构。

　 2. 总体设计要画流程图。

　 3. 提供程序测试方案。

　 4. 界面友好。

2.3需求分析

根据要求，需要在系统中建立无向图。系统应该有高度灵活性，可以由用户根据当前交通网络图输入初始数据，并且可以更改。系统根据用户的输入建立无向图的结构，并通过狄克斯特拉算法和弗洛伊德算法实现要求，并提供两种功能供用户选择。

2.4 算法描述

录入城市及道路数据 预置城市间的距离

构 建 交 通 网 交通查询系统 根据无向图建立查询功能 查询一个城市到其它城市的最短路径 查询任意两城市间的最短路径 狄克斯特拉算法的具体流程图

开 始 初始化距离和路径 i=1 i++ j=1;j++;jn 修改最短路径和距离 输出结果

弗洛伊德算法的具体流程图

开 始 初始化距离和路径 设为从到的只以集合中的节点为中间节点的最短路径的长度 最短路径不经过点k 最短路径经过点k 输出结果

三、概要设计：

程序中将涉及下列两个抽象数据类型：一个是图，一个是队列。

　 1、设定“图”的抽象数据类型定义：

ADT Graph{

数据对象 V：V 是具有相同特性的数据元素的集合,称为顶点集。

　 数据关系 R：

R={VR}

VR = {| v, w ∈VP(v, w), 表示从v到w的弧， 谓词P(v, w)定义了弧 的意义或信息} 基本操作 P：

CreateGraph( D[v1]=0； //S集初始时只有源点，源点到源点的距离为0； While (S集中顶点数和是否存在。如果存在，则比较和的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求出的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短路径。

4.4 建立有向图的存储结构

void CreateMGraph(MGraph * G,int n,int e) {

int i,j,k,w;

for(i=1;ivexs[i]=(char)i; for(i=1;iarcs[i][j]=Maxint;

printf(\输入%d条边的i,j及w:\\n\,e); for(k=1;k

#include

#define Num 288 //定义常量Num #define Maxint 31111

enum boolean{FALSE,TRUE}; //定义布尔类型 typedef char VertexType; typedef int Adjmatrix; typedef struct

{ VertexType vexs[Num]; //顶点数组， 类型假定为char型 Adjmatrix arcs[Num][Num];

}MGraph; // 邻接矩阵， 假定为int型 int D1[Num],P1[Num];

int D[Num][Num],P[Num][Num];

void CreateMGraph(MGraph *G,int n,int e); //采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数

void Dijkstra(MGraph *G,int v1,int n); //狄克斯特拉算法的声明 void Floyd(MGraph *G,int n); //弗洛伊德算法的声明 void main()

{ MGraph *G;

system(\ //定义无向图G int n,e,v,w,k;

int m=1;

G=(MGraph *)malloc(sizeof(MGraph));

printf(\printf(\ 欢迎使用交通查询系统 *\\n\

printf(\ printf(\输入完文本后，均以Enter结束!*\\n\ printf(\输入顶点和边数时请使用“,”号隔 *\\n\ printf(\开!!! *\\n\ printf(\

printf(\

printf(\使用查询功能前，请输入顶点个数和边数n,e：\

scanf(\

CreateMGraph(G,n,e); tf(\ printf(\ 请选择：1 或 2 ，选择 0 退出：\\n\ scanf(\

if(m==2){ Floyd(G,n);

printf(\请输入起点和终点，用“,”号隔开：\\n\ scanf(\ k=P[v][w];

if(k==0)

printf(\输出的结果：\\n顶点%d到%d无路径!\\n\

else {

printf(\输出的结果：\\n从顶点%d到%d的最短路径是: %d\ while(k!=w){ printf(\→%d\

k=P[k][w]; }

printf(\→%d\

printf(\ 路径长度: %d\\n\

} }

else

if(m==1){

printf(\请输入起点编号：\\n\ scanf(\ Dijkstra(G,v,n); }

}

printf(\程序已结束!谢谢您的使用!\\n\

}

void CreateMGraph(MGraph *G,int n,int e) //构建城市的无向图

{

int i,j,k,w;

for(i=1;ivexs[i]=(char)i; for(i=1;iarcs[i][j]=Maxint; //距离初始化 if(i==j)

G->arcs[i][j]=0;

}

printf(\请输入%d条边的i,j,及w： \\n\ for(k=1;karcs[i][j]=w; //建立城市之间的距离 }

printf(\地图的结构建立成功！\\n\

}

void Dijkstra(MGraph *G,int v1,int n) //狄克斯特拉算法求一个城市到任意一个城市的距离

{ int D2[Num],P2[Num]; int v,i,w,min; }

enum boolean S[Num];

for (v=1;varcs[v1][v]; //距离初始化

P2[v]=v1;

if(D2[v]<Maxint) // 路径初始化

else P2[v]=0;

P2[v1]=0;S[v1]=TRUE; //源点V1放入s中 for(i=2;i<n;i++){ //循环直至所有顶点的最都求出

min=Maxint; //Maxint置最小长度初值 for(w=1;w<=n;w++) //选不在S中且有最小顶点w

if(!S[w]

•  下载文档
•  收藏
•  分享 赏
•  0