实验5 最短路径


实验时间

4-6课时。

实验目的

1. 掌握图的存储结构。
2. 掌握Dijkstra算法或Floyd算法。

问题描述

给定全国铁路网,对于任意一对城市,找出它们之间的最短路径经过哪些城市,并输出最短路径的长度。
铁路网的信息以文本形式给出,其格式为:
城市A编号 城市B编号 距离
其中城市编号和城市名称信息也是以文本形式给出,其格式为:
编号 城市名称
这两个文本文件可以在这里下载

实验内容

1. 以北京作为起始点,对铁路网分别做深度优先遍历和广度优先遍历。
2. 求出下列城市之间的最短路径:沈阳至西安、呼和浩特至成都、上海至乌鲁木齐。
3. 从铁路网中删除一些城市(例如郑州),再重新计算上述城市之间的最短路径。

实现提示

图的存储结构可使用邻接矩阵(较为简单)或邻接表。