《数据结构课程设计》最短路径问题实验报告

目 录

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

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

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

算机建立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从A城到B城途中中转次数最少；如何选择一条路径使得从A城到B城里程最短；如何选择一条路径使得从A城到B城花费最低等等的一系列问题。

二、系统分析

设计一个交通咨询系统，能咨询从任何一个城市顶点到另一城市顶点之间的最短路径(里程)、最低花费或是最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或是所需费用等信息。

针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题、对任意一对顶点间最短路径问题三个问题，这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。并未本系统设置一人性化的系统提示菜单，方便使用者的使用。

1

三、概要设计

可以将该系统大致分为三个部分：

① 建立交通网络图的存储结构； ② 解决单源最短路径问题；

③ 实现两个城市顶点之间的最短路径问题。

交通咨询系统 建立图的 存储结构 义 迪杰斯特拉算法（单源最短路径） 费洛依德算法（任意顶点对间最短路径）

迪杰斯特拉算法流图：

2

弗洛伊德算法流图：

3

4