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

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

学 生 姓 名 学 号 指 导 教 师

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 >| v, w ∈VP(v, w), < v, w > 表示从v到w的弧， 谓词P(v, w)定义了弧 < v, w > 的意义或信息} 基本操作 P：

CreateGraph(&G,V,VR);

初始条件：V 是图的顶点集，VR 是图中弧的集合。 操作结果：按 V 和 VR 的定义构造图。

LocateVex(G,u);

初始条件：图 G 存在，u 和 G 中的顶点有相同特征。

操作结果：若 G 中存在顶点 u，则返回该顶点在图中位置；否则返回其他

信息。

First_next_adj（G，v） ；

初始条件：图 G 存在，v 是 G 中某个顶点。

操作结果：返回 V 的第一个邻接顶点。若顶点在 G 中没有邻接顶点，则返

回“空” 。

DFSTraverse(G,i);

初始条件：图 G 存在，i 为某个顶点在邻接矩阵中的位置。 操作结果：以 i 为起始点，对图进行深度优先遍历。 BFSTraverse(G,i);

初始条件：图 G 存在，i 为某个顶点在邻接矩阵中的位置。

操作结果：以 i 为起始点，对图进行广度优先遍历。 ｝ADT Graph

2、设定队列的抽象数据类型定义：

ADT Queue{

数据对象：D={ a i a i ∈ BiTree, i ∈ N+ }

数据关系：R1={< a i , a i ?1 >| a i ?1 , a i ∈ D ,i=2,…，n}

约定 a1 端为队列头， a n 端为队列尾。

基本操作： InitQueue(&Q)

操作结果：构造一个空队列 Q。 EnQueue(&Q,&e)

初始条件：队列 Q 已存在。

操作结果：插入元素 e 为 Q 的新的队尾元素。 DeQueue(&Q)

初始条件：队列 Q 已存在。

操作结果：删除 Q 的对头元素，并返回其值。 QueueEmpty(&Q)

初始条件：队列 Q 已存在。

操作结果：若 Q 为空队列，则返回 1，否则 0。 QueueLenghth(Q)

初始条件：队列 Q 已存在。

操作结果：返回 Q 的元素个数，即队列长度。 GetHead（Q，&e）

初始条件：Q 为非空队列。

操作结果：用 e 返回 Q 的对头元素。 } ADT Queue

3、本程序包含三个模块

1）主程序模块 void main( ) {

选择欲建图的类型；

构建图并对其用邻接矩阵的形式打印；

对图进行深度和广度优先搜索以及求某个顶点的第一邻接点； 求某一源点到其余顶点的最短路径。 ｝

2）图模块——实现图的抽象数据类型和基本操作 3）队列模块——实现队列的抽象数据类型及今本操作

3.1 程序流程图

四、详细设计：

4.1建立图的存储结构

首先定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

?Wij，若(vi,vj)或?vi,vj??E(G);?。A[i，j]=?0或?，当不满足上述条件时

当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。 图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点i的信息。因此，图的邻接矩阵的存储结构定义如下： #definf MVNum 88 //最大顶点数 typedef struct { VertexType vexs[MVNum]; //顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum]; //邻接矩阵，假定为int型 }MGraph; 4.2单源最短路径

最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们希望找出从某个源点S?V到G中其余各顶点的最短路径。

为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。

那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。

迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，V?{v1,v2,?,vn}，cost是表示G的邻接矩阵，cost[i][j]表示有向边的权。若不存在有向边，则cost[i][j]的权为无穷大（这里取值为32767）。设S是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点v1为源点，集合S的初态只包含一个元素，即顶点v1。数组dist记录从源点到其他顶点当前的最短距离，其初值为dist[i]=cost[v1][i],i=1,2,??,n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中顶点，把w加入集合S

中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到V-S为空。

最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。

因此，迪杰斯特拉算法可用自然语言描述如下： 初始化S和D，置空最短路径终点集，置初始的最短路径值； S[v1]=TRUE; D[v1]=0； //S集初始时只有源点，源点到源点的距离为0； While (S集中顶点数

任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要对G中任意一对顶点有序对“v,w(v?w)”,找出v到w的最短路径。

要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。

这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。

费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点 vi到vj的最短路径。如果从vi到vj存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较和< vi,v1,vj >的路径长度，取长度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于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;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++)

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

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

scanf(\,&i,&j,&w); G->arcs[i][j]=w; }

printf(\有向图建立完毕\\n\); }

4.5迪杰斯特拉算法

void Dijkstra(MGraph *G,int v1,int n) {

int D2[MVNum],P2[MVNum]; int v,i,w,min;

enum boolean S[MVNum]; for(v=1;v<=n;v++) {

S[v]=FALSE;

D2[v]=G->arcs[v1][v]; if(D2[v]

P2[v]=0; }

D2[v1]=0;S[v1]=TRUE; for(i=2;i

min=Maxint;

for(w=1;w<=n;w++) if(!S[w]&&D2[w]

v=w;min=D2[w]; }

S[v]=TRUE;

for(w=1;w<=n;w++)

if(!S[w]&&(D2[v]+G->arcs[v][w]

D2[w]=D2[v]+G->arcs[v][w]; P2[w]=v; } }

printf(\路径长度 路径\\n\ for(i=1;i<=n;i++) {

printf(\

printf(\ while(v!=0) {

printf(\,v); v=P2[v]; }

printf(\); } }

4.6弗洛伊德算法

void Floyd(MGraph *G,int n) {

int i,j,k,v,w; for(i=1;i<=n;i++) for(j=1;j<=n;j++) {

if(G->arcs[i][j]!=Maxint) P[i][j]=j; else

P[i][j]=0;

D[i][j]=G->arcs[i][j]; }

for(k=1;k<=n;k++) {

for(i=1;i<=n;i++) for(j=1;j<=n;j++) {

if(D[i][k]+D[k][j]

D[i][j]=D[i][k]+D[k][j]; P[i][j]=P[i][k];; } } } }

4.7 运行主控程序

void main() {

MGraph *G;

int m,n,e,v,w,k; int xz=1;

G=(MGraph *)malloc(sizeof(MGraph)); printf(\输入图中顶点个数和边数n,e:\ scanf(\

CreateMGraph(G,n,e); while (xz!=0) {

printf(\求城市间的最短路径******\\n\ printf(\求一个城市到所有城市的最短路径\\n\ printf(“2.求任意的两个城市之间的最短路径\\n\ printf(\请选择：1 或 2,选择 0 退出:\ scanf(\ if(xz==2) {

Floyd(G,n);

printf(\输入起点和终点:v,w:\ scanf(\ k=P[v][w]; if(k==0)

printf(\顶点 %d 到 %d 无路径!\\n\ else {

printf(\从顶点%d到%d的最短路径是::%d\ while(k!=w) {

printf(\

k=P[k][w]; }

printf(\

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

else if(xz==1) {

printf(\求单源路径，输入源点 v :\ scanf(\ Dijkstra(G,v,n); } }

printf(\结束求最短路径\}

五、运行与测试：

1、进入查询系统并设置城市个数及城市间连接情况

2、进入查询界面，按要求“1”进行查询

3、在查询界面，按要求“2”进行查询

4、退出查询界面

六、：总结与心得

在第一次编译时出现了很多错误，是因为我对C语言的不熟练，比如调用费洛伊德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出结果。最后把调到外面才能运行。

通过本实验基本掌握了这两个算法的应用，编程过程中有过很多失误，可知对平时的学习还有很多不够仔细的地方，通过这次设计，我学到了很多。

附录：程序代码

#include

#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); //调用CreateMGraph有向图函数 while(m!=0){

printf(\===============\\n\

printf(\ ^_^ 求城市之间的最短路径 ^_^ \\n\ printf(\ printf(\求一个城市到其他所有城市的最短路径\\n\ printf(\求任意的两个城市之间的最短路径\\n\ printf(\ 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;i<=n;i++) //以任意城市i出发为起点 G->vexs[i]=(char)i; for(i=1;i<=n;i++)

for(j=1;j<=n;j++) //任意城市j为终点

{

G->arcs[i][j]=Maxint; //距离初始化 if(i==j)

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

}

printf(\请输入%d条边的i,j,及w： \\n\ for(k=1;k<=e;k++) {

scanf(\

G->arcs[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;v<=n;v++)

{ S[v]=FALSE; //s[]置空 D2[v]=G->arcs[v1][v]; //距离初始化

P2[v]=v1;

if(D2[v]

else P2[v]=0;

P2[v1]=0;S[v1]=TRUE; //源点V1放入s中 for(i=2;i

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

if(!S[w]&&D2[w]

S[v]=TRUE; for(w=1;w<=n;w++) //顶点w加入s中 if(!S[w]&&(D2[v]+G->arcs[v][w]

{

D2[w]=D2[v]+G->arcs[v][w]; P2[w]=v; } }

printf(\输出的结果：\\n\

printf(\路径长度 路径\\n\ //输出最短路径

for(i=1;i<=n;i++){ printf(\

printf(\ while(v!=0){ printf(\←%d\ v=P2[v]; }

printf(\ }

}

void Floyd(MGraph *G,int n) //用弗洛伊德算法求任意两顶点最短距离 { }

int i,j,k; //定义三个变量 for(i=1;i<=n;i++)

for(j=1;j<=n;j++) { if(G->arcs[i][j]!=Maxint) //距离初始化 P[i][j]=j; //路径初始化

else P[i][j]=0;

D[i][j]=G->arcs[i][j]; }

for(k=1;k<=n;k++) //以k为源点循环求出所有顶点的最短路径 { }

for(i=1;i<=n;i++) //i为已知最短路径的顶点

for(j=1;j<=n;j++) //j为未知最短路径的顶点 { if(D[i][k]+D[k][j]

D[i][j]=D[i][k]+D[k][j]; P[i][j]=P[i][k];

本文来源：https://www.bwwdw.com/article/rvzd.html