目 录 一、概述 ......................................... 1 二、系统分析 ..................................... 1 三、概要设计 ..................................... 2 四、详细设计 ..................................... 5 4.1 建立图的存储结构 ........................... 5 4.2 单源最短路径 ............................... 6 4.3 任意一对顶点之间的最短路径 ................. 7 五、运行与测试 ................................... 8 参考文献 ........................................ 11 附录 ............................................ 12 1 交通咨询系统设计（最短路径问题） 一、概述 在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A 城到B 城途中中转次数最少；如何选择一条路径使得从A 城到B 城里程最短；如何选择一条路径使得从A 城到B 城花费最低等等的一系列问题。 二、系统分析 设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。 针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。 2 三、概要设计 可以将该系统大致分为三个部分： ① 建立交通网络图的存储结构； ② 解决单源最短路径问题； ③ 实现两个城市顶点之间的最短路径问题。 迪杰斯特拉算法流图： 交通咨询系统 费洛依德算法（任意顶点对间最短路径） 建 立图 的存 储结 构义 迪杰斯特拉算法（单源最短路径） 3 弗洛伊德算法流图： 4 5 四、详细设计 4 .1 建立图的存储结构 定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设 G=(V,E)是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下定义的n 阶方阵。 ...
