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

1、问题描述：若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。基本要求：（1） 从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。（2） 以用户指定的起点和终点，输出从起点到终点的花费。一、 需求分析：1、本程序需要用矩阵来存储图的各种信息。2、测试数据输入（文件）51 10 3 20 11 1 1 5 11 2 1 1 151 1 1 1 111 1 1 1 1 （用户）起点 0终点 4 输出18实现提示 ：（1） 设图的顶点大于1个，不超过30个，每个顶点用

2、一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, , n-1）。（2） 此题为求有向网中顶点间最短路径问题，可建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。（3） Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。（4） 考虑没有路径时的输出。二、概要设计 ： 抽象数据类型 ：为实现上述功能需建立一个二维数组和图类。 算法的基本思想 ：1、图的信息的读取：定义一个二维数组，将图的信息读入，并将两边距离为-1的边转换为一个较大的数（>>

3、;途中各点之间的距离）。2、Dijkstra算法：根据输入的第一个结点首先找到（直接距离）该点最近的A，则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。如果l1<l2，则用l1的距离替换l2。重复上述操作n-1（n为结点数）次。得到的即为第一个结点到其他结点的最短距离。程序的流程 程序由三个模块组成： 输入模块： 读入图的信息（用矩阵进行存储）。处理模块：Dijkstra算法。输出模块：将收入结点到其他点的最短距离输出。 三、详细设计 算法的具体步骤：#define N 30int aNN; class Graph private: int ver;

4、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<ver;i+) for(int j=0;j<ver;j+) cin>>temp; if(temp=-1) /-1表示两点之间无直接联系，将距离赋为500 aij=1000; else aij=temp; void Graph:Dijkstra(int start

5、,int end) /最小路径的算法 int distN,sN; int i,j,min,pos; for(i=0;i<ver;i+) if(i=start) si=1; /标记边是否被访问 else si=0; for(i=0;i<ver;i+) disti=astarti; /该点到其他边的距离 for(i=0;i<ver-1;i+) /共有n个顶点，故要重复n-1 min=500;pos=0; for(j=0;j<ver;j+) if(sj=0 && distj<min) min=distj; /找出最小边,则该边是最短路径所必须的 pos=

6、j; spos=1; for(j=0;j<ver;j+) if(distj>distpos+aposj) /如过通过pos这条边的距离小于原先的距离 distj=distpos+aposj; /改变距离 for(i=0;i<ver;i+) if(i!=start) /不会有起点到起点的路径 cout<<start<<"->"<<i<<":"<<disti<<endl; int main() int v,start,end; cin>>v; Grap

7、h G(v); G.build(); cin>>start>>end; G.Dijkstra(start,v-1); system("pause"); return 0; 四、调试分析 略。 五、测试结果 本实验的测试结果截图如下：注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。六、用户使用说明（可选） 1 、本程序的运行环境为windows 操作系统，执行文件为zuiduanlu.exe 2 、运行程序时 提示输入数据 并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。七、实验心得（可选） 1、 编写本程序时，一开始对

8、读入的数据未进行处理，使得Dijkstra比较繁琐，后来经改正，在读入时对数据进行处理，使代码简洁了一些。2、 一开始对算法的一些细节没有仔细考略，具体for循环执行多少次就可以完成相应的操作，由于测试数据有限，一开始为发现错误。后来仔细分析，改掉了错误。附录（实验代码）： #include<iostream>using namespace std;#define N 30int aNN; class Graph private: int ver; public: Graph(int v)ver=v; void build(); void Dijkstra(int start,in

9、t end); void printf(int start); ;void Graph:build() /构建图 int temp,max=1000; for(int i=0;i<ver;i+) for(int j=0;j<ver;j+) cin>>temp; if(temp=-1) /-1表示两点之间无直接联系，将距离赋为500 aij=1000; else aij=temp; void Graph:Dijkstra(int start,int end) /最小路径的算法 int distN,sN; int i,j,min,pos; for(i=0;i<ver;

10、i+) if(i=start) si=1; /标记边是否被访问 else si=0; for(i=0;i<ver;i+) disti=astarti; /该点到其他边的距离 for(i=0;i<ver-1;i+) /共有n个顶点，故要重复n-1 min=500;pos=0; for(j=0;j<ver;j+) if(sj=0 && distj<min) min=distj; /找出最小边,则该边是最短路径所必须的 pos=j; spos=1; for(j=0;j<ver;j+) if(distj>distpos+aposj) /如过通过pos这条边的距离小于原先的距离 distj=distpos+aposj; /改变距离 for(i=0;i<ver;i+) if(i!=start) /不会有起点到起点的路径 cout<<start<<"->"<<i<<":"<<disti&