内容发布更新时间 : 2024/5/10 10:02:40星期一 下面是文章的全部内容请认真阅读。

目 录 一、概述 ......................................... 1 二、系统分析 ..................................... 1 三、概要设计 ..................................... 2 四、详细设计 ..................................... 5 4.1 建立图的存储结构 ........................... 5 4.2 单源最短路径 ............................... 6 4.3 任意一对顶点之间的最短路径 ................. 7 五、运行与测试 ................................... 8 参考文献 ........................................ 11 附录 ............................................ 12

交通咨询系统设计（最短路径问题）

一、概述

在交通网络日益发达的今天，针对人们关心的各种问题，利用

计算机建立一个交通咨询系统。在系统中采用图来构造各个城市之

间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，

所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提

出的各种问题，例如：如何选择一条路径使得从 A 城到 B 城途中中

转次数最少；如何选择一条路径使得从 A 城到 B 城里程最短；如何

选择一条路径使得从 A 城到 B 城花费最低等等的一系列问题。

二、系统分析

设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城

市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对

于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用

等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在

实际情况中的最短路径问题，本系统中包括了建立图的存储结构、

单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以

上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设

置一人性化的系统提示菜单，方便使用者的使用。

0

三、概要设计 可以将该系统大致分为三个部分： 1 建立交通网络图的存储结构； 2 解决单源最短路径问题； 3 实现两个城市顶点之间的最短路径问题。 建立 图的 存储 结构 义 交通咨询系统 迪杰斯 特拉算 法（单 源最短 路径） 费洛依 德算法 （任意 顶点对 间最短 路径） 迪杰斯特拉算法流图： 1