(完整word版)数据结构实验报告最短路径.doc

HUNANUNIVERSITY

课程实习报告

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

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