《数据结构教学规划》最短路径问答实验报告

~目 录一、概述 1二、系统分析 1三、概要设计 2四、详细设计 54.1建立图的存储结构 54.2单源最短路径 64.3任意一对顶点之间的最短路径 7五、运行与测试 8参考文献 11附录 12~交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计感谢阅读算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的精品文档放心下载联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权精品文档放心下载值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种谢谢阅读问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；感谢阅读如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使精品文档放心下载得从A城到B城花费最低等等的一系列问题。二、系统分析设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市感谢阅读顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不感谢阅读同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。精品文档放心下载针对最短路径问题，在本系统中采用图的相关知识，以解决在实谢谢阅读际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源精品文档放心下载最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个感谢阅读问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性谢谢阅读化的系统提示菜单，方便使用者的使用。~三、概要设计可以将该系统大致分为三个部分：①建立交通网络图的存储结构；②解决单源最短路径问题；③实现两个城市顶点之间的最短路径问题。交通咨询系统迪杰建立斯特图的拉算存储法（单结构源最义短路径）

费洛依德算法（任意顶点对间最短路径）迪杰斯特拉算法流图：~弗洛伊德算法流图：~~四、详细设计4.1建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关精品文档放心下载系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有感谢阅读如下定义的n阶方阵。W，若(V,V)或V,VE(G)谢谢阅读 ij i j i jA[i,j]0或，其他情况注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点Vi的信息）。邻接矩阵的存储结构：感谢阅读#defineMVNum100//最大顶点数typedefstruct{VertexTypevexs[MVNum];//顶点数组，类型假定为char型Adjmatrixarcs[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是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V为源点，集合S的初态只包含顶点V。数组dist记录精品文档放心下载1 1从源点到其它各顶点当前的最短距离，其初值为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之间的最短路径的前驱顶点。谢谢阅读ij2i2jiji1j~4.3任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(V≠W)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。精品文档放心下载费洛伊德算法的基本思想：假设求从V到V的最短路径。如果感谢阅读i j存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径<v,v>和<v,v>是否存在。如果存谢谢阅读i 1 1 j在，则比较路径<v.v>和<v,v,v>的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑感谢阅读感谢阅读i j那么<v,…,v,…,v>可分解为<v,…,v>和<v,…,v>，而这两条路谢谢阅读i 2 j i 2 2 j径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径<v,…,v,…v>的长度。将该长度与前一次中求得谢谢阅读i 2 j的从v到v的中间顶点序号不大于1的最短路径比较，取其长度较精品文档放心下载i j短者作为当前求得的从v到v的中间顶点序号不大于2的最短路径。感谢阅读i j依此类推……直至顶点v加入当前从v到v的最短路径后，选出从感谢阅读n i j到v的中间顶点序号不大于n的最短路径为止。由于图G中顶点序感谢阅读j号不大于n，所以v到v的中间顶点序号不大于n的最短路径，已考精品文档放心下载i j虑了所有顶点作为中间顶点的可能性，因此，它就是v到v的最短谢谢阅读i j~路径。五、运行与测试测试实例1：利用如下图所示的有向图来测76 74664242656455测试实例2：利用下图求交通网络图（无向图）的最短路径。精品文档放心下载2553北京1704西安2695徐州8124成都5113349郑州565115792368上海13857广州 6实例1运行结果：~~实例2运行结果：~六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手，精品文档放心下载进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心谢谢阅读的各种问题（当然此次试验最终主要解决的问题是：最短路径问题）。精品文档放心下载这次试验中我深刻的了解到了树在计算机中的应用是如何的神谢谢阅读奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别感谢阅读是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉谢谢阅读算法、弗洛伊德算法等，对树的学习有了一个更深的了解。精品文档放心下载参考文献【1】《数据结构》严蔚敏.清华大学出版社.【2】《数据结构课程设计》苏仕华.极械工业出版社.~附录#include<stdio.h>#include<stdlib.h>#defineMVNum100#defineMaxint32767enumboolean{FALSE,TRUE};typedefcharVertexType;typedefintAdjmatrix;typedefstruct{VertexTypevexs[MVNum];Adjmatrixarcs[MVNum][MVNum];精品文档放心下载}MGraph;intD1[MVNum],p1[MVNum];intD[MVNum][MVNum],p[MVNum][MVNum];精品文档放心下载voidCreateMGraph(MGraph*G,intn,inte)感谢阅读{inti,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("%d,%d,%d",&i,&j,&w);感谢阅读G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕！\n");精品文档放心下载}voidDijkstra(MGraph*G,intv1,intn)精品文档放心下载{intD2[MVNum],p2[MVNum];intv,i,w,min;enumbooleanS[MVNum];for(v=1;v<=n;v++){S[v]=FALSE;D2[v]=G->arcs[v1][v];if(D2[v]<Maxint)p2[v]=v1;else~p2[v]=0;}D2[v1]=0;S[v1]=TRUE;for(i=2;i<n;i++){min=Maxint;for(w=1;w<=n;w++)if(!S[w]&&D2[w]<min){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[w]=D2[v]+G->arcs[v][w];感谢阅读p2[w]=v;}}printf("路径长度 路径\n");for(i=1;i<=n;i++){printf("%5d",D2[i]);printf("%5d",i);v=p2[i];while(v!=0){printf("<-%d",v);v=p2[v];}printf("\n");}}voidFloyd(MGraph*G,intn)精品文档放心下载{inti,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;elsep[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];}}}}voidmain(){MGraph*G;intm,n,e,v,w,k;intxz=1;G=(MGraph*)malloc(sizeof(MGraph));谢谢阅读printf("输入图中顶点个数和边数n,e:");谢谢阅读scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0){printf("************求城市之间最短路径************\n");感谢阅读printf("=========================================\n");printf("1.求一个城市到所有城市的最短路径\n");printf("2.求任意的两个城市之间的最短路径\n");printf("=========================================\n");printf("请选择:1或2，选择0退出:\n");scanf("%d",&xz);精品文档放心下载if(xz==2){Floyd(G,n);printf("输入源点（或起点）和终点:v,w:");谢谢阅读scanf("%d,%d",&v,&w);k=p[v][w];if(k==