数据结构实验报告十一―最短路径问题.doc

问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所基本要求：（1） 从文件中读入有向网中顶点的数量和顶点间的票价的矩阵2） 以用户指定的起点和终点，输出从起点到终点的花费一、 需求分析：1、本程序需要用矩阵来存储图的各种信息2、测试数据 输入（文件） 5 －1 10 3 20 －1－1 －1 －1 5 －1－1 2 －1 －1 15－1 －1 －1 －1 11－1 －1 －1 －1 －1 （用户）起点 0终点 4 输出 18实现提示 ：（1） 设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）2） 此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。

4） 考虑没有路径时的输出二、概要设计 ： 抽象数据类型 ：为实现上述功能需建立一个二维数组和图类 算法的基本思想 ：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>途中各点之间的距离）2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2如果l1>temp; if(temp==-1) //-1表示两点之间无直接联系，将距离赋为500 a[i][j]=1000; else a[i][j]=temp; } }void Graph::Dijkstra(int start,int end){ //最小路径的算法 int dist[N],s[N]; int i,j,min,pos; for(i=0;idist[pos]+a[pos][j]) //如过通过pos这条边的距离小于原先的距离 dist[j]=dist[pos]+a[pos][j]; //改变距离 } } for(i=0;i"<>v; Graph G(v); G.build(); cin>>start>>end; G.Dijkstra(start,v-1); system("pause"); return 0; }四、调试分析 略。

五、测试结果 本实验的测试结果截图如下：注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入六、用户使用说明（可选） 1 、本程序的运行环境为windows 操作系统，执行文件为zuiduanlu.exe 2 、运行程序时 提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果七、实验心得（可选） 1、 编写本程序时，一开始对读入的数据未进行处理，使得Dijkstra比较繁琐，后来经改正，在读入时对数据进行处理，使代码简洁了一些2、 一开始对算法的一些细节没有仔细考略，具体for循环执行多少次就可以完成相应的操作，由于测试数据有限，一开始为发现错误后来仔细分析，改掉了错误附录（实验代码）： #includeusing namespace std;#define N 30int a[N][N]; class Graph{ private: int ver; public: Graph(int v){ver=v;} void build(); void Dijkstra(int start,int end); void printf(int start); };void Graph::build(){ //构建图 int temp,max=1000; for(int i=0;i>temp; if(temp==-1) //-1表示两点之间无直接联系，将距离赋为500 a[i][j]=1000; else a[i][j]=temp; } }void Graph::Dijkstra(int start,int end){ //最小路径的算法 int dist[N],s[N]; int i,j,min,pos; for(i=0;idist[pos]+a[pos][j]) //如过通过pos这条边的距离小于原先的距离 dist[j]=dist[pos]+a[pos][j]; //改变距离 } } for(i=0;i"<>v; Graph G(v); G.build(); cin>>start>>end; G.Dijkstra(start,v-1); system("pause"); return 0; }。