Floyd算法的矩陣形式

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

【關(guān)鍵詞】Floyd算法 矩陣 網(wǎng)路 最短路徑

【中圖分類號】G642 【文獻(xiàn)標(biāo)識碼】A 【文章編號】1674-4810（2015）03-0070-02

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

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

一 Floyd算法簡介

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

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

二 Floyd算法的矩陣形式

1.基本概念

2.矩陣形式的Floyd算法

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

步驟1：輸入權(quán)矩陣D（0）=D，k=1；

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

步驟3：若k

三 實(shí)例

通過右圖給出的例子，

具體說明如何應(yīng)用矩陣形

式的Floyd算法求出網(wǎng)絡(luò)

中任意兩點(diǎn)之間的距離。

首先，得到網(wǎng)絡(luò)G的

鄰接矩陣D如下：

步驟1：輸入權(quán)矩陣D（0）=D，k=1；

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

〔責(zé)任編輯：龐遠(yuǎn)燕〕