用一個(gè)例子說明Floyd算法

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

下面是一個(gè)使用弗洛伊德算法求圖中所有頂點(diǎn)對(duì)之間最短路徑的示例:

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

　　A -> B: 3

　　A -> C: 8

　　A -> D: -4

　　B -> C: 1

　　B -> D: 7

　　C -> D: 2

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

　　| 0 3 8 -4 |

　　| INF 0 1 7 |

　　| INF INF 0 2 |

　　| INF INF INF 0 |

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

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

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

算法運(yùn)行后，最終矩陣將是:

　　| 0 3 4 0 |

　　| INF 0 1 7 |

　　| INF INF 0 2 |

　　| INF INF INF 0 |

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