数据结构课程设计最短路径问题实验报告要点x
时间:2020-11-09 12:46:38 来源:勤学考试网 本文已影响 人
、概述
、系统分析 三、概要设计 四、详细设计
4.1建立图的存储结构
4.2单源最短路径
4.3任意一对顶点之间的最短路径
1112五、运行与测试 参考文献 附录
11
12
PAGE
PAGE #
交通咨询系统设计(最短路径问题)
、概述
在交通网络日益发达的今天,针对人们关心的各种问题,利用计 算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的 联系,图中顶点表示城市,边表示各个城市之间的交通关系,所带权 值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种 问题,例如:如何选择一条路径使得从 A城到B城途中中转次数最少;
如何选择一条路径使得从 A城到B城里程最短;如何选择一条路径使
得从A城到B城花费最低等等的一系列问题。
、系统分析
设计一个交通咨询系统,能咨询从任何一个城市顶点到另一城市 顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不 同的咨询要求,可输入城市间的路程、所需时间或是所需费用等信息。
针对最短路径问题,在本系统中采用图的相关知识,以解决在实
单源际情况中的最短路径问题,本系统中包括了建立图的存储结构、 最短问题、对任意一对顶点间最短路径问题三个问题, 这对以上几个 问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性 化的系统提示菜单,方便使用者的使用。
单源
、概要设计
可以将该系统大致分为三个部分:
建立交通网络图的存储结构;
解决单源最短路径问题;
实现两个城市顶点之间的最短路径问题。
交通咨询系统
立 的 储 构
t
叩
迪杰
费洛依
斯特
德算法
拉算
(任意
法(单
顶点对
源最
间最短
短路
路径)
径)
迪杰斯特拉算法流图:
弗洛伊德算法流图:
\>l\
四、详细设计
4.1建立图的存储结构
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关
系的矩阵。设G=(V,E)是具有n个顶点的图,贝J G的邻接矩阵是具有
如下定义的n阶方阵。
Wj,若(Vi,Vj)或 C Vi,Vj 沁 E(G)
A[i,j]」
0或处,其他情况
注:一个图的邻接矩阵表示是唯一的!其表示需要用一个二维数
组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有
n个元
素的一维数组来存储顶点信息(下标为i的元素存储顶点
Vi的信息)。
邻接矩阵的存储结构:
#define MVNum 100 // 最大顶点数
typ edef struct
VertexT ype vexs[MVNum];// 顶点数组,类型假定为
char 型
Adjmatrix arcs[MVNum][MVNum];// 邻接矩阵,假定为 int 型
}MGra ph;
注:由于有向图的邻接矩阵是不对称的,故程序运行时只需要输
入所有有向边及其权值即可。
4.2单源最短路径
单源最短路径问题:已知有向图(带权),期望找出从某个源点S € V到G中其余各顶点的最短路径。
迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。
是表,则算法思想:设有向图G=(V,E),其中V二{1,2 ,……n}, cost
是表
,则
示G的邻接矩阵,
表示有向边<i,j>的权。若不存在有向边 <i,j>
cost[i][j] 的权为无穷大(这里取值为32767)。设S是一个集合, 集合中一个元素表示一个顶点,从源点到这些顶点的最短距离已经求 出。设顶点Vi为源点,集合S的初态只包含顶点V。数组dist记录 从源点到其它各顶点当前的最短距离,其初值为dist[i]=
cost[i][j] , i=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]。重复上述过程,直到S中包含V中其余顶点的最短路 径。
最终结果是:S记录了从源点到该顶点存在最短路径的顶点集合, 数组dist记录了从源点到V中其余各顶点之间的最短路径,path是 最短路径的路径数组,其中path[i]表示从源点到顶点i之间的最短 路径的前驱顶点。
4.3任意一对顶点之间的最短路径
任意顶点对之间的最短路径问题,是对于给定的有向网络图
G=(V,E),要对G中任意一对顶点有序对,“V,W(VMW)”找出V到W
的最短路径。而要解决这个问题,可以依次把有向网络图中每个顶点 作为源点,重复执行前面的迪杰斯特拉算法n次,即可求得每对之间 的最短路径。
费洛伊德算法的基本思想:假设求从 V到V的最短路径。如果
存在一条长度为arcs[i][j] 的路径,该路径不一定是最短路径,还 需要进行n次试探。首先考虑路径<^21>和vvi,Vj>是否存在。如果存 在,则比较路径<V.Vj>和<Vi,Vi,Vj>的路径长度,取长度较短者为当 前所求得。该路径是中间顶点序号不大于 1的最短路径。其次,考虑
从Vi到Vj是否包含有顶点V2为中间顶点的路径<Vi,…,V 2,…,V j>,若
没有,则说明从Vi到Vj的当前最短路径就是前一步求出的;若有, 那么<Vi,…,V2,…,Vj>可分解为<Vi,…,V2>和<V2,…,Vj>,而这两条路 径是前一次找到的中间点序号不大于 1的最短路径,将这两条路径长
度相加就得到路径<Vi,…,V 2,…Vj>的长度。将该长度与前一次中求得
的从Vi到Vj的中间顶点序号不大于1的最短路径比较,取其长度较 短者作为当前求得的从Vi到Vj的中间顶点序号不大于2的最短路径。
依此类推……直至顶点Vn加入当前从Vi到Vj的最短路径后,选出从
Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序
号不大于n,所以Vi到Vj的中间顶点序号不大于n的最短路径,已考
虑了所有顶点作为中间顶点的可能性,因此,它就是 Vi到Vj的最短
路径。
五、运行与测试
测试实例1利用如下图所示的有向图来测试
徐州
实例1运行结果:
W iinclows\5ystem32\Debug\a sdfga sg .exe'
^—i 点的 顶边 中条 图饬:!-h?nT」三刊 ■址,
^—i 点的 顶边 中条 图饬:!
-h?nT」三刊 ■
址,
2 14
14
6 6
4-
6 6ri—
Ll^ 有
径 路 !短 X 立N ■4ull _J 1 4 储一一 存一一 的一一
i
1 短短 有市 到个 -任 RUK
请选择=1
请选择=1或2,选择0退出=
萦单源蚩径,畅入源点“ =1
跖径长《 路隹
0
45
13
91
136
71
17
1
3<-1 4<-7<-1 5<-4<-7<-1 &<-2<-3<-1
7<-1
—求城市之间最短路径
1 i i
1 i i 曇取 市间 城之 到个 市两 s -任 ruk -.V --v
请选择记或2,
请选择记或2,选扌¥?退岀:
2
W淞点總籬潼;
径路长度:讣
实例2运行结果:* 'CAW indows\sy5te m32\De bugt/d fg 咼 sy 亡艰[名 £11,3,675 3
实例2运行结果:
* 'CAW indows\sy5te m32\De bugt/d fg 咼 sy 亡艰
[名 £1
1,3,675 3丄"5
1.4.704
4.1.704
2.3.511
2,5 詡 12 5,2,812
3.4.349
3,6,1579 6,3^1579
4.7.651
5」②&g 6,5,2368 6,7,138E |7,6,1385
8
短短
曇取
请选择U或2,选择0退出:
¥.单源矍径,输入源点"江 路径长? 路g
1
2<-3<-1
3<-1
4<-1
5<-2<-3<-1
6<-3<-1
7<-4<-1
F求城帀之间最短路径
G
12 0G
695
704 2018 2274 13SE
8
&& pfpt. 恒溟
1A.+A
************求城市 之 间 最短路径**卄*********
S 短短 曰曆甌 帀间 城N 有帀 到个 市两 WS $ 一任 i
请选择汉或2,选择D退岀=
2
舲1? £躋点>齧盞4话灌;;一1—4—7径路长度泛323
"KmmcK求城市之' 可最短路径幵开开REHt枯
2 -隶任i苗两个城帀之间的叢短$薯桓
请选择或2,选择邑退出:
2
领入源点(或起点〕利终点:u,w:7,2
A顶点7至r 2最短路径路径是:7-4-3-2径路长度皿“
六、总结与心得
该课程设计主要是从日常生活中经常遇到的交通网络问题入手, 进而利用计算机去建立一个交通咨询系统,以处理和解决旅客们关心 的各种问题(当然此次试验最终主要解决的问题是: 最短路径问题)。
这次试验中我深刻的了解到了树在计算机中的应用是如何的神 奇与灵活,对于很多的问题我们可以通过树的相关知识来解决,特别 是在解决最短路径问题中,显得尤为重要。
经过着次实验,我了解到了关于树的有关算法,如:迪杰斯特拉 算法、弗洛伊德算法等,对树的学习有了一个更深的了解。
参考文献
【1】《数据结构》严蔚敏.清华大学出版社.
【2】《数据结构课程设计》苏仕华.极械工业出版社.
附录
#in clude<stdio.h>
#in clude<stdlib.h> #defi ne MVNum 100
#define Maxi nt 32767 enum boolea n{FALSE,TRUE}; typ edef char VertexT ype;
typ edef int Adjmatrix;
typ edef struct{
VertexT ype vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGra ph;
int D1[MVNum], p1[MVNum];
int D[MVNum][MVNum], p[MVNum][MVNum]; 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]=Maxi nt; printf("输入 %d 条边的 i.j 及 w:\n",e); for(k=1;k<=e;k++){
scan f("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=w;
}
printf("有向图的存储结构建立完毕! \n");
}
void Dijkstra(MGraph *G ,int v1,int n) {
int D2[MVNum], p2[MVNum];
int v,i,w,mi n;
en um boolean S[MVNum]; for(v=1;v<=n; v++){
S[v]=FALSE; D2[v]=G->arcs[v1][v]; if(D2[v]<Maxi nt) p2[v]=v1;
else
p2[v]=0;
}
D2[v1]=0; S[v1]=TRUE;
for(i=2;i< n; i++){
mi n=Maxi nt;
for(w=1;w<=n; w++)
if(!S[w] && D2[w]<mi n)
{v=w;mi n=D2[w];} S[v]=TRUE;
for(w=1;w<=n; w++)
if(!S[w] && (D2[v]+G->arcs[v][w]<D2[w])){ D2[w]=D2[v]+G->arcs[v][w]; p2[w]=v;
}
路径\n");} printf("路径长度
路径\n");
prin tf("%5d",D2[i]);
prin tf("%5d",i);v= p2[i]; while(v!=O){ prin tf("<-%d",v);
v=p 2[v];
} prin tf("\n");
}
}
void Floyd(MGra ph *G,i nt n)
{
int i,j,k,v,w;
for(i=1;i<=n ;i++) for(j=1;j<=n;j++)
{
if( G->arcs[i][j]!=Maxi nt)
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][j]=D[i][k]+D[k][j]; p[i][j]=p[ i][k];
}
}
}
void mai n()
{
MGra ph *G;
int m, n,e,v,w,k;
int xz=1;
G=(MGra ph *)malloc(sizeof(MGra ph)); printf("输入图中顶点个数和边数 n ,e:");
scan f("%d,%d", &n,& e);
CreateMGra ph(G, n,e);
while(xz!=0){
求城市之间最短路径 ************
求城市之间最短路径 ************ n");
=============================\n");
prin tf(”========
printf("1.求一个城市到所有城市的最短路径 \n");
printf("2.求任意的两个城市之间的最短路径 \n");
:\n");prin tf(”====================================== printf(”请选择:1或2,选择0退出:\n");
:\n");
scan f("%d",& xz);
if (xz==2){
Floyd(G, n);
printf("输入源点(或起点)和终点 :v,w:");
scan f("%d,%d", &v,&w);
k=p[v][w];
if (k==0)
printf(” 顶点 %d 到 %d 无路径!\n",v,w); else
{
printf(”从顶点%d至U %d 最短路径路径是:%d",v,w,v);
while (k!=w){
prin tf("--%d",k);
k=p [k][w];
}
prin tf("--%d",w);
printf(” 径路长度:%d\n",D[v][w]);
}
}
else
if(xz==1)
printf(”求单源路径,输入源点 v :”); scan f("%d",&v); Dijkstra(G,v, n);
}
printf("结束求最短路径,再见!\n");
}