弗洛伊德算法（Floyd-Warshall算法）是一種用於查找圖中所有頂點對之間的最短路徑的算法。它是一種動態規劃算法，可以處理帶有正權或負權邊的加權圖，但要求圖中沒有負權重環路。該算法在1962年由羅伯特·弗洛伊德提出，以其名字命名以表彰其在計算機科學領域的貢獻。
算法的基本思想是通過逐步引入中間頂點來更新頂點間最短路徑的估計值。具體來說，算法使用三重循環來遍歷所有頂點對，並在每次疊代中嘗試通過引入一個新的中間頂點來改進已知頂點對之間的最短路徑。如果通過添加這箇中間頂點能夠找到一條更短的路徑，則更新該路徑的長度。
算法的步驟可以概括為：
初始化距離矩陣，將圖中各邊的權值作為鄰接矩陣的元素。
使用三重循環遍歷所有頂點對和中間頂點。
對於每一對頂點i和j，以及中間的頂點k，如果通過k的路徑比直接從i到j的路徑短，則更新距離矩陣。
重複上述步驟，直到所有中間頂點都被考慮過。
該算法的時間複雜度和空間複雜度均為O(V^2)，其中V是圖中的頂點數。這意味著它非常適合處理稠密圖，但在稀疏圖中可能不是最優選擇。弗洛伊德算法的主要優點是它可以找到任意兩點之間的最短路徑，而不僅僅是最開始指定的起點到終點的路徑。它的缺點在於時間複雜度較高，對於大型圖可能導致執行時間較長。
此外，弗洛伊德算法的一個變種是考慮了邊的權重為負數的情況，這允許處理包含負權重邊的圖。這種變種在處理某些特定問題時非常有用，例如在路徑規劃或網路流問題中。