3.1 弗洛伊德算法原理和实现

弗洛伊德算法是用于解决任意两点间最短路径的一种算法，可以正确处理有向图的最短路径问题，同时也用于计算有向图的传递闭包。

3.1.1 弗洛伊德算法的原理

为了说明弗洛伊德算法，下面举一个例子。暑假即将来临前，小美准备去一些城市旅游。有些城市之间有公路，有些城市之间没有公路，如图3.1所示。为了节省经费，以及方便计划旅程，小美希望在出发之前知道任意两个城市之间的最短路径。

从图3.1可知，4个城市之间有8条公路，公路上的数字表示这条公路的长短。图3.1中的公路是单向的。现在的需求是计算两个城市之间的最短路程，也就是求任意两点之间的最短路径。现在，需要一个数据结构来存储图的信息，可以用一个4×4的二维矩阵 e _4×4 来存储，即

从上面的矩阵可知，从编号为1的城市到编号为2的城市的路径为2，则 e ［1］［2］=2。因为2号城市无法直接到达4号城市，则 e ［2］［4］=∞。此外，约定编号为 i 的城市达到编号为 i 的城市路径为0，即 e ［1］［1］=0、 e ［2］［2］=0、 e ［3］［3］=0、 e ［4］［4］=0。

现在遇到的问题是，如何求取两个城市之间的最短路径呢？显然，通过深度优先搜索或者广度优先搜索可以求出两点之间的最短路径。所以，进行 n ² 遍的深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，就可以求取任意两点之间的最短路径。还有没有其他方法？

换个角度思考，根据一些常识，如果要让任意两点（如从 a 点到 b 点）之间的路径变短，只能引入第3个点（如 k 点），即路径从原来的 a 直接到 b （ a → b ）改成从 a 经过 k 到 b （ a → k → b ），这样才可能缩短原来从 a 点到 b 点的路径。那么，这个中间的 k 点是1~ n 中的哪个点呢？甚至有时候不是只通过一个点，而是经过两个或更多的点才能使路径变得更短，即 a → k ₁ → k ₂ → b ，或 a → k ₁ → k ₂ →…→ b 。例如，对于图3.1，从编号为4到编号为3的城市，其路径 e ［4］［3］=12。如果通过编号为1的城市进行中转，即4→1→3，则为 e ［4］［1］+ e ［1］［3］=5+6=11，路径将由12缩短为11。其实，编号为1到编号为3的城市也可以通过编号为2的城市中转，即1→2→3，则 e ［1］［2］+ e ［2］［3］=5，路径由6缩短为5。所以，从编号为4到编号为3的城市，经过编号为1和编号为2的城市进行中转，即4→1→2→3，路径为 e ［4］［1］+ e ［1］［2］+ e ［2］［3］=5+2+3=10，路径进一步缩短为10。

当任意两点之间不允许经过第三点时，城市之间的最短路径就是式（3.1）给出的初始路径。

假设现在只允许经过编号为1的点，求任意两点之间的最短路径，应该如何处理？只要判断 e ［ i ］［1］+ e ［1］［ j ］是否小于 e ［ i ］［ j ］即可。其中， e ［ i ］［1］表示从编号为 i 到编号为1的城市的路径长度， e ［1］［ j ］表示从编号为1到编号为 j 的城市的路径长度。其中， i 是1~ n 的循环， j 也是1~ n 的循环，用C代码描述，如代码清单3-1所示。

执行该代码后，在经过编号为1城市的情况下，任意两点之间的最短路径更新为

因此，通过式（3.2）可知，在经过编号为1的城市的情况下，编号为3到编号为2的城市 e ［3］［2］，编号为4到编号为2的城市 e ［4］［2］，以及编号为4到编号为3的城市 e ［4］［3］的路径都变短了。式（3.2）中带有阴影的数字表示变短的路径。

接下来，继续尝试求解在经过编号为1的城市和编号为2的城市的情况下任意两点之间的最短路径。其实很简单，只需要判断 e ［ i ］［2］+ e ［2］［ j ］是否比 e ［ i ］［ j ］的路径更短。

用C代码描述，如代码清单3-2所示。

执行该代码后，在经过编号为1和编号为2的城市的情况下，任意两点之间的最短路径更新为

因此，通过式（3.3）可知，在增加经过编号为2的城市的情况下，编号为1到编号为3的城市路径 e ［1］［3］和编号为4到编号为3的城市路径 e ［4］［3］都变短了。式（3.3）中带有阴影的数字表示变短的路径。

同理，继续在只允许经过编号为1、2和3的城市进行中转的情况下，求任意两点之间的最短路径，更新为

式（3.4）中带有阴影的数字表示变短的路径。

最后，允许通过所有编号的城市作为中转，任意两点之间最终的最短路径表示为

式（3.5）中带有阴影的数字表示变短的路径。

总结上面的过程，可以用代码清单3-3所示的C语言代码求从 i 城市到 j 城市之间的最短路径。

需要注意，弗洛伊德算法不能解决带有“负权值回路”（或者叫“负权值环”）的图，因为带有“负权值回路”的图没有最短路径。

进一步，将弗洛伊德算法描述为

（1）定义 P （ i , j , k ）表示从 v _i 到 v _j ，由序号不大于 k 的顶点为中间点（或直达）可构成的最短路径。

（2）初始化从 v _i 到 v _j 的目前已知较短路径为从 v _i 到 v _j 的直达弧（没有经过中间点）。

（3）对每两顶点对（ v _i , v _j ）依次计算 P （ i , j , k ）， k =0，…， n -1，计算规则为

P ( i , j , k )=min( P ( i , k , k -1)+ P ( k , j , k -1), P ( i , j , k -1))

因此，最终可以通过类似代码清单3-3给出的三重for循环完成基于弗洛伊德算法的两点间最短路径的求取。

3.1.2 C语言程序设计

本节将介绍如何使用C语言实现弗洛伊德算法。在使用C语言实现该算法前，构造一个由顶点和边构成的有向图，如图3.2所示。图3.2中，顶点个数为5。

用邻接矩阵表示图3.2中顶点之间的连接关系，即

注 ：矩阵中顶点之间无连接关系，则用∞表示。

在使用C语言实现式（3.6）所示的邻接矩阵关系时，将无连接关系用INF表示，且将其定义为一个较大的整数。

实现弗洛伊德算法的C语言代码如代码清单3-4所示。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_3_1目录中，使用LoongIDE软件工具打开example_3_1.lxp工程文件。

3.1.3 C语言编译和调试

本节将介绍如何对设计工程进行编译，并将设计下载到龙芯1B开发板进行验证。具体实现步骤如下所示。

（1）编译程序代码，给龙芯1B硬件开发平台上电。

（2）启动并配置PuTTY工具。

（3）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器模式，开始运行程序，在PuTTY命令行界面中将打印出原始邻接矩阵和经过弗洛伊德算法更新后的邻接矩阵，如图3.3所示。

3.1.4 汇编语言程序设计

实现弗洛伊德算法的汇编语言代码如代码清单3-5所示。

注 ：读者可以定位到本书提供资源的\loongson1B_training_example\example_3_2目录中，使用LoongIDE软件工具打开example_3_2.lxp工程文件。

3.1.5 汇编语言编译并调试

本节将介绍如何对前面所设计的汇编语言代码进行编译，并在龙芯1B硬件开发平台上进行调试和验证。具体实现步骤如下所示。

（1）编译程序代码，并给龙芯1B硬件开发平台上电。

（2）如图3.4所示，在代码清单3-5中设置第一个断点。

（3）如图3.5所示，在代码清单3-5中设置第二个断点。

（4）在LoongIDE主界面主菜单下，选择Debug->Run，进入调试器界面，程序自动停到第一个断点的位置。

（5）在LoongIDE调试器界面右侧的“CPU Register”标签页中，找到并用鼠标左键双击寄存器名字为“v0”的一行。

（6）弹出“View Memory”对话框，如图3.6所示。在图3.6中可知，以一维数组所表示的邻接矩阵的起始地址为0x802124b8。在该对话框中，按如下设置参数。

① Count：25（通过“Count”标题右侧的旋转按钮设置）。

② Data Type：unsigned char（通过选择“unsigned char”前面的复选框设置）。

（7）单击“Fetch”按钮，即可在图3.6中看到以存储地址0x802124b8开始连续的25个字节中保存着以一维数组形式表示的邻接矩阵，与代码清单3-5数据段中给出的数组arr中的数据元素的值完全相同。

（8）单击图3.6中的按钮图标 ，退出“View Memory”对话框。

（9）在LoongIDE主界面主菜单下，选择Debug->Run，程序停在第二个断点处。

（10）在LoongIDE调试器界面右侧的“CPU Register”标签页中，找到并用鼠标左键双击寄存器名字为“v0”的一行。

（11）弹出“View Memory”对话框，如图3.7所示。

图3.7给出了执行完弗洛伊德算法后用一维数组arr所表示的邻接矩阵。根据该一维数组arr给出的邻接矩阵信息，将其还原为邻接矩阵，如式（3.7）所示。