数据结构实验报告最短路径.doc

HUNAN UNIVERSITY

课程实习报告

题 目： 最短路径
学生姓名：
学生学号：
专业班级：
指导老师：
完成日期：

一、 需求分析
乘汽车旅行的人总希望找出到目的地的尽可能短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？
计算机网络中的路由就是通过互联的网络把信息从源地址传输到目的地址的活动。为了高效引导数据的传输，如何找出源和目的地址之间的最优路径？
这些问题中的网络（交通网，计算机通信网）可以使用一个带权图来建模，寻找最优路的需求可转换为带权图的最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和边组成的）中两结点之间的最短路径。
二、 概要设计
抽象数据类型
从文件中读入有向网中顶点的数量和顶点间的票价的矩阵。
以用户指定的起点和终点，输出从起点到终点的花费。
算法的基本思想
用有向网表示某地区的公路交通网，其中顶点表示该地区的一些主要场所，弧表示已有的公交线路，弧上的权表示票价。。
程序的流程
（1） 设图的顶点大于1个，不超过30个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为0, 1, 2, 3, …, n-1）。
（2） 可Dijkstra算法中有一个辅助向量D，表示当前所找到的从源点到其它点的最短路径长度。因为每次都要在D中找最小值，为提高性能，用最小值堆的优先队列存储D值。
三、 详细设计
算法的具体步骤
建立以票价为权的邻接矩阵，用Dijkstra算法求最短路径长度。
输入和输出的格式
输入：
首先输入顶点的数量，然后是各顶点对应的字母，再输入各条弧（权值都置为1）。
输出：
输出从首个顶点开始的广度优先遍历序列和深度先遍历序列。
四、 测试数据
输入
（文件）
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
五、运行结果