18

二、 概要设计

为实现上述功能需要用到图的存储结构。

利用邻接矩阵构造图，并求出某一顶点到另一顶点的最短路径并

打印输出。

三、 算法基本思想

根据题目要求用弗洛伊德算法可以实现两点最短路径问题。弗洛

伊德算法仍然使用图的邻接矩阵arcs[n+1][n+1]来存储带权有向图。

算法的基本思想是:设置一个n x n的矩阵A(k)，其中除对角线的元素

都等于0外，其它元素a(k)[i][j]表示顶点i到顶点j的路径长度，K

表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路

径长度，没有有向边时，路径长度为∞，当K=0时, A (0)[i][j]=arcs[i][j]，

以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间

顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原

路径，修改矩阵元素。

四、 程序设计流程

程序由三个模块组成：

1.输入模块：起点终点和各点间的权值这都从文件中读取。

2.求最短路径模块：通过弗洛伊德算法求出起点终点最短路径。

3.输出模块：完成弗洛伊德算法后，把最短路径给出，并给出具

体路径。

五、 程序源代码