弗羅特方法（Floyd method）在有向網路上求 所有點對之間最短有向路的一種方法.
基本介紹
- 中文名：弗羅特方法
- 外文名：Floyd method
介紹
弗羅特方法(Floyd method )在有向網路上求 所有點對之間最短有向路的一種方法.已有求自一 點到其餘各點最短有向路的計算方法，只要將這個 方法使用n次，就可求出所有點對之間的最短有向 路，但這樣做計算量太大.弗羅特方法是比此更好的 算法.設U;;表示自點i到點7且不經過點m,m十1, .. ,n(除去點i和點7)的最短有向路的長度，則自點 i到點7不經過m- l,m- 2,w,n(除去點i和點7) 的最短有向路長度U獷'=minU翼,U m- Um; .當m =n時，U獷‘就等於網路中自點i到點，的最短有向 路的長度.具體算法如下:
弗羅特方法
3.若m=n，則步驟終止.根據(<r;; >內的記錄尋找出所有i和7之間的最短有向路.若min，則m=m- 1，返回步驟2. 弗羅特算法的計算量為0＜n3 ).
