“數據結構”課程中Ｆｌｏｙｄ算法教學方法研究

文章編號：1672-5913(2008)08-0123-02

摘要：Floyd算法是“數據結構”課程里的一個經典算法，但其原理卻難以掌握，影響到該算法的教學效果。本文從求最短路徑的基本思想出發，對Floyd算法的原理進行了剖析，并給出了該算法的正確性證明，有助于學生理解和掌握該算法。

關鍵詞：最短路徑；Floyd；教學方法；數據結構

中圖分類號：G642

文獻標識碼：B

1引言

求圖中兩頂點之間的最短路徑算法是“數據結構”課程在圖論章節里面的重點內容，其在通信網絡、電力網絡及交通網絡等地理信息系統中有著廣泛的應用。解決最短路徑問題有兩個經典的算法，即Dijkstra(迪杰斯特拉)算法和Floyd(弗洛伊德)算法。前者一次可以求出圖中一個給定頂點到達其他所有頂點之間的最短路徑，時間復雜度為O(n2)；而Floyd算法則可以一次求出圖中所有任意兩個頂點之間的最短路徑，時間復雜度為O(n3)。

雖然可以將圖中每個頂點作為起始頂點，逐一調用Dijkstra算法來完成Floyd算法同樣的功能，時間復雜度也是O(n3)，但Floyd算法從形式上更簡潔一些。遺憾的是，雖然許多文獻資料對Floyd算法的思想和實現均有論述，然而依然難以理解，影響到了該算法的教學和學習效果。本文從求最短路徑的基本原理出發，給出了該算法思路的正確性證明，有助于學生理解和掌握該算法。

2Floyd算法的基本思想

對于任意給定的圖 ，V為頂點集合，E為弧的集合。設該圖有 個頂點，不失一般性，令其分別為 。Floyd算法不斷的在圖中任意一對頂點Vi與Vj( )之間的路徑中加入一個新頂點Vk(即k從1變化到n)，并計算出只經過迄今為止所引入的頂點的所有可能路徑的最短值。依次類推，直到包含了圖中所有頂點為止。Floyd算法的步驟如下：

Step1：定義并初始化輔助矩陣 和 ，矩陣元素 與 分別用來保存頂點Vi與Vj之間的最短距離和最短路徑(由于最短路徑的源點Vi與終點Vj都是已知的，故 只保存路徑中途徑其它頂點的部分)。矩陣 與 的初始值分別記錄所有Vi與Vj之間直接到達(中間不途徑其它頂點)時的最短距離與最短路徑。當 時，若兩個頂點之間沒有弧相連，將 置為∞，否則將 置為弧的權值；當 時，使 。令 (沒有途徑其它頂點，故為空)。

Step2：定義變量k，并將其初始值置為1；

從上面給出Floyd算法步驟可以看出，該算法過程極為簡捷，然而，為何經過這樣的運算得到的就是Vi與Vj之間的最短距離，下面我們給出該算法的正確性證明。

3Floyd算法的正確性證明

路徑即在圖上從一個頂點到達另外一個頂點所經過的頂點序列，欲求出圖中任意兩個頂點Vi到Vj( )之間的最短距離，最樸素的想法就是求出Vi到Vj之間所有可能存在的簡單路徑(最短路徑必然是簡單路徑，故本文中只考慮簡單路徑)，從中選取一個最短的即可。Vi到Vj所有可能的簡單路徑如表1所示。若直接按照上述順序進行計算，則計算量極其巨大，Floyd算法實際上采用最短路徑累積的方法，大大降低了計算的復雜度。

在證明里，我們使用符號 表示Vi與Vj之間途徑頂點 時所有可能簡單路徑的集合以及 ，其中 表示Vi與Vj直接到達。例如 表示 。下面給出Floyd算法的正確性證明：

首先我們對Vi與Vj之間的路徑構成采用結構歸納法[4]證明將頂點Vk引入到Vi與Vj之間并計算最短路徑時，已考慮了途徑頂點V1，…，Vk以及直接到達的所有可能的情況，即已經考慮了途徑集合 中所有可能的路徑。

歸納基礎：在算法的Step1里，對輔助矩陣 與 進行初始化，分別記錄所有Vi與Vj之間直接到達(途徑頂點的集合為空集 ，即經過的路徑集合為 )時的最短距離與最短路徑，此時考慮的途徑路徑的集合為 ，顯然直接到達時成立(圖1)。

圖1直接到達

歸納步驟：假設引入頂點Vk( ，當 即為歸納基礎)時命題成立，此時 與 保存的是頂點Vi與Vj之間途徑集合 時最短路徑和最短距離。

當引入頂點 時，此時從頂點Vi經過路徑集合 到達頂點Vj有兩種方案(如圖2所示)：1)從Vi經過路徑集合 直接到達頂點Vj；2)從Vi途徑路徑集合 到達頂點Vk+1，再從頂點Vk+1途徑路徑集合 到達頂點Vj。根據算法Step3的運算規則，如果方案2)的距離更短，即 ，則同時更新 與 ，即保存經過頂點Vk+1的最短距離和路徑；否則保持不變。此時已經考慮的路徑集合為

，

為了便于下面的說明，令其為路徑集合A。下面需要證明路徑集合A包含 。

對于 中的路徑 ，只能有以下兩種可能的形式：

1) 中不包含 ，即 的所有的頂點均來自 ，顯然 。

2) 中包含 ，設其形為 ，顯然 與 均不包含 。從1)可知 且 ，從而有

因此已考慮了途徑集合 的所有情況，亦成立。

最后，我們證明對于任意給定的圖 ，Floyd算法的確考慮了表1中列舉的Vi與Vj之間最短路徑的所有情況，并正確計算出了最短路徑。

圖2引入頂點

由于圖頂點個數的有窮性，在頂點Vi與Vj之間途徑的路徑中逐次引入頂點 。當引入頂點Vn并經過計算，根據前面的證明，可知已考慮了途徑路徑集合的所有情況。在途徑路徑集合上加上已知的源點Vi與終點Vj，已考慮的最短路徑集合為{Vi} {Vj}，顯然考慮了表1中列舉的最短路徑的所有可能情況。因此在比較了最短路徑的所有可能后， 與 內保存的是從頂點Vi到達Vj的最短距離以及途徑的最短路徑。

參考文獻

[1] 嚴尉敏，吳偉民. 數據結構(C語言版)[M]. 北京:清華大學出版社，1997:186-192.

[2] 耿國華. 數據結構—C語言描述[M]. 北京:高等教育出版社，2005:234-240.

[3] G. Winsekl著. 宋國新譯. 程序設計語言的形式語義[M]. 北京:機械工業出版社，2004.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”