floyd算法介紹 floyd算法是什麼

1、Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

2、在計算機科學中，Floyd-Warshall算法是一種在具有正或負邊緣權重（但沒有負週期）的加權圖中找到最短路徑的算法。算法的單個執行將找到所有頂點對之間的最短路徑的長度（加權）。 雖然它不返回路徑本身的細節，但是可以通過對算法的簡單修改來重建路徑。 該算法的版本也可用於查找關係R的傳遞閉包，或（與Schulze投票系統相關）在加權圖中所有頂點對之間的最寬路徑。

3、Floyd-Warshall算法是動態規劃的一個例子，並在1962年由Robert Floyd以其當前公認的形式出版。然而，它基本上與Bernard Roy在1959年先前發表的算法和1962年的Stephen Warshall中找到圖形的傳遞閉包基本相同，並且與Kleene的算法密切相關 在1956年）用於將確定性有限自動機轉換為正則表達式。算法作為三個嵌套for循環的現代公式首先由Peter Ingerman在1962年描述。

4、該算法也稱為Floyd算法，Roy-Warshall算法，Roy-Floyd算法或WFI算法。