实验11 最短路径问题实验报告.doc

《实验11 最短路径问题实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验11最短路径问题实验报告通信2班谢宗欣叶恒张琼背景乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和边组成的）中两结点之间的最短路径。问题具体的形式包括：l确定起点的最短路径问题，即已知起始结点，求最短路径的问题

2、。适合使用Dijkstra算法。l确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。l确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。l全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。问题描述若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。基本要求（1）从文件中读入有

3、向网中顶点的数量和顶点间的票价的矩阵。（2）以用户指定的起点和终点，输出从起点到终点的花费。测试数据输入（文件）5－110320－1－1－1－15－1－12－1－115－1－1－1－111－1－1－1－1－1（用户）起点0终点4输出18实现提示（1）设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0,1,2,3,…,n-1）。（2）此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。（3）Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。因为每次都要在D中

4、找最小值，为提高性能，用最小值堆的优先队列存储D值。（4）考虑没有路径时的输出。抽象数据类型用二维数组实现邻接矩阵主要函数MarkgetMark(Docu*D,inti)voidsetMark(Docu*D,intv,Markm)intfirst(Docu*D,intv)intnext(Docu*D,intv,intw)intweight(Docu*D,intv,intw)intminVertex(Docu*D,int*B)voidDijkstra(Docu*D,int*B,ints)算法实现#include#include#include

5、ib>#includeusingnamespacestd;enumMark{UNVISITED,VISITED};typedefstructDocuNode{intn;Markm;}DocuNode;typedefstructDocu{intn;DocuNode*Node;int**edge;}Docu;MarkgetMark(Docu*D,inti){returnD->Node[i].m;}voidsetMark(Docu*D,intv,Markm){D->Node[v].m=m;}intfirst(Docu*D,intv){inti;for(i=0;in;i+

6、+)if((D->edge[v][i])!=-1)returni;returni;}intnext(Docu*D,intv,intw){inti;for(i=w+1;in;i++)if((D->edge[v][i])!=-1)returni;returni;}intweight(Docu*D,intv,intw){returnD->edge[v][w];}intminVertex(Docu*D,int*B){inti,v;for(i=0;in;i++)if(getMark(D,i)==UNVISITED){v=i;break;}for(i++;in;i++)if(g

7、etMark(D,i)==UNVISITED&&((((B[i]

8、

9、(B[v]==-1))))v=i;returnv;}voidDijkstra(Docu*D,int*B,ints){inti,v,w;for(i=0;in;i++){v=minVertex(D,B);if(B[v]==-1)return;setMark(D,v,VISITED);for(w=first(D,v);