1
实验报告一
一．题目要求
输入Ｎ（Ｎ<10）个城市，每两个城市之间有对应的距离和费用（可以不能到达），要
求实现如下程序：
ａ）给出任意两个城市之间的最短距离，及其到达方式；
ｂ）给出任意两个城市之间的最小费用，及其到达方式；
ｃ）权衡距离和费用，给出任意两个城市之间的最优路径，及其到达方式；
PS：1. 距离矩阵和费用矩阵由同学自己给出；
2. 题 c)的最优路径由自己定义。
二．算法设计：
欲求得每一对顶点之间的最短路径，解决这一问题的办法是采用弗洛伊德算法。
弗洛伊德算法仍从图的带权邻接矩阵出发，其主要思想是：设集合 S 的初始状态
为空集合，然后依次向集合 S 中加入顶点 V0,V1,V2，…，Vn-1，每次加入一个顶点，
我们用二维数组 D 保存每一对顶点之间的最短路径的长度，其中，D[i][j]存放从顶点 Vi
到 Vj 的最短路径的长度。在算法执行中，D[i][j]被定义为：从 Vi 到 Vj 的中间只经过 S
中的顶点的所有可能的路径中最短路径的长度（如果从 Vi 到 Vj 中间只经过 S 中的顶
点当前没有路径相通，那么 d[i][j]为一个大值 MaxNum）。即 d[i][j]中保存的是从 Vi 到
Vj 的“当前最短路径”的长度。每次加入一个新的顶点，Vi 和 Vj 之间可能有新的路径
产生，将它和已经得到的从 Vi 到 Vj 的最短路径相比较，d[i][j]的值可能需要不断修正，
当 S=V 时，d[i][j]的值就是从 Vi 到 Vj 的最短路径。
因为初始状态下集合 S 为空集合，所以初始化 D[i][j]=A[i][j]（A[i][j]是图的邻接矩
阵）的值是从 Vi 直接邻接到 Vj，中间不经过任何顶点的最短路径。当 S 中增加了顶点
V0,那么 D(0)[i][j]的值应该是从 Vi 到 Vj，中间只允许经过 v0 的当前最短路径的长度。
为了做到这一点，只需对 D(0)[i][j]作如下修改：
D(0)[i][j]=min{D[i][j],D[i][0]+D[0][j]}
一般情况下，如果 D(k-1)[i][j]是从 Vi 到 Vj，中间只允许经过{ V0,V1,V2，…，
Vk-1}的当前最短路径的长度，那么，当 S 中加进了 Vk，则应该对 D 进行修改如下:
D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}
三．概要设计：
1.数据结构
二维数组来表示邻接矩阵，数组中存储元素表示邻接点之间的距离，或费用。
2.抽象数据类型
有向图
3.函数接口
Void main() 主函数
Void Dispmat() 输出邻接矩阵函数
Void Floyed() 计算最短路径函数
Void Dispath() 输出最短路径函数
四．详细设记
Main 函数的流程图如下：
