弗洛伊德演算法資料 弗洛伊德演算法介紹

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

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