弗洛伊德算法（Floyd's algorithm）是一種用于求帶權(quán)圖中最短路徑的算法，適用于帶有正負(fù)權(quán)邊的圖（但不能有負(fù)環(huán)）。這種算法也有時被稱為弗洛伊德-沃爾什算法。該算法基于動態(tài)規(guī)劃，其時間復(fù)雜度為O（V^3），其中V是圖中的頂點數(shù)。此外，該算法還可用于檢測圖中的負(fù)環(huán)并求出傳遞閉包。

 

下面是一個使用弗洛伊德算法求圖中所有頂點對之間最短路徑的示例:

假設(shè)我們有一個具有4個頂點（A，B，C和D）的圖，以及以下帶權(quán)邊：

　　A -> B: 3

　　A -> C: 8

　　A -> D: -4

　　B -> C: 1

　　B -> D: 7

　　C -> D: 2

 

我們可以用矩陣表示每對頂點之間的距離，其中第i行第j列的元素表示從頂點i到頂點j的最短距離。最初，我們將矩陣設(shè)置為圖中邊的值：

　　| 0 3 8 -4 |

　　| INF 0 1 7 |

　　| INF INF 0 2 |

　　| INF INF INF 0 |

 

然后我們使用弗洛伊德算法來更新矩陣:

對于 k = 1 到 V (V 是頂點數(shù))，其中V = 4:

1. 對于 i = 1 到 V:
2. 對于 j = 1 到 V:
3. 如果 dist[i][j] > dist[i][k] + dist[k][j]，則更新 dist[i][j] = dist[i][k] + dist[k][j]

算法運行后，最終矩陣將是:

　　| 0 3 4 0 |

　　| INF 0 1 7 |

　　| INF INF 0 2 |

　　| INF INF INF 0 |

從這個矩陣中，我們可以看出從頂點A到頂點B的最短距離是3，從A到C是4，從A到D是0，從B到C是1等。