实验6最短路径问题解答.doc

HUNAN UNIVERSITY 数据结构实验报告 学生姓名 学生学号 专业班级 实验6:最短路径问题 背景 乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？ 这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。 问题具体的形式包括： ? 确定起点的最短路径问题，即已知起始结点，求最短路径的问题。适合使用Dijkstra算法。 ? 确定终点的最短路径问题，与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 ? 确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径。 ? 全局最短路径问题，求图中所有的最短路径。适合使用Floyd-Warshall算法。 问题描述： 若用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。试设计一个交通咨询系统，指导乘客以最少花费从该地区中的某一场所到达另一场所。 基本要求 （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的 边转换为一个较大的数（途中各点之间的距离）。 Dijkstra算法： 根据输入的第一个结点首先找到（直接距离）该点最近的A， 则这两点之间的边是必须的，然后比较通过A到其他点的距离l1和直接到其他点的距离l2。如果l1l2，则用l1的距离替换l2。重复上述操作n-1（n为结点数）次。得到的即为第一个结点到其他结点的最短距离。 程序的流程： 输入模块： 读入图的信息（用矩阵进行存储）。 处理模块：Dijkstra算法。 输出模块：将收入结点到其他点的最短距离输出。 代码: #includeiostream #define N 30 using namespace std; int 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;iver;i++) for(int j=0;jver;j++){ cintemp; 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;iver;i++) { if(i==start) s[i]=1; //标记边是否被访问 else