Floyd算法的矩陣形式

【摘 要】Floyd算法可以求出網絡中任意兩點間的最短距離，但是，許多學生都感到Floyd算法很難掌握。究其原因，是Floyd算法的計算公式形式復雜，不容易理解和記憶。筆者給出Floyd算法的矩陣形式，并通過實例進行說明。

【關鍵詞】Floyd算法 矩陣 網路 最短路徑

【中圖分類號】G642 【文獻標識碼】A 【文章編號】1674-4810（2015）03-0070-02

最短路問題是最重要的優化問題之一，不僅可以用于解決路徑優化問題，如設備更新、管道鋪設、電路設計、選址等，還是解決很多優化問題的有力工具。

所謂最短路問題，就是求出網絡中任意兩點之間權重最小的路徑。這類問題可以通過反復使用Dijkstra算法進行求解，但比較煩瑣。Floyd算法可以直接求出網絡中任意兩點間的最短距離。但是，該算法需要多次使用迭代公式進行計算，學生不容易掌握。鑒于此，本文給出Floyd算法的矩陣形式，并通過一個簡單的例子進行說明，從而使學生對該算法有更加深入的理解。

一 Floyd算法簡介

最后，我們得到D（n）=（ ）n×n，元素 即為點vi到點vj的最短距離。

從上述步驟可看出，算法需要迭代n次，每次需要利用迭代公式計算n2個元素的值，并且迭代公式的形式不容易記憶。鑒于此，下面給出Floyd算法的矩陣形式。

二 Floyd算法的矩陣形式

1.基本概念

2.矩陣形式的Floyd算法

矩陣形式的Floyd算法的主要步驟如下：

步驟1：輸入權矩陣D（0）=D，k=1；

步驟2：設ck是矩陣D（k-1）的第k列，rk是矩陣D（k-1）的第k行，令：D（k）=D（k-1） （ck rk）；

步驟3：若k

三 實例

通過右圖給出的例子，

具體說明如何應用矩陣形

式的Floyd算法求出網絡

中任意兩點之間的距離。

首先，得到網絡G的

鄰接矩陣D如下：

步驟1：輸入權矩陣D（0）=D，k=1；

步驟2：令c1=（0，7，5，6，∞，∞，∞，∞）T，r1=（0，7，5，2，∞，∞，∞，∞），得到：

〔責任編輯：龐遠燕〕