弗洛伊德算法是計算無向有權圖中兩點間最短路徑的算法，復雜度為O(n^3)。其思路是將兩點間距離分為過（指定的）第三點或是不過，然后取它們的最小值，如此循環就可以得到兩點之間真正的最小值。

void floyd() {for (int k = 0; k < n; ++k){for (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){//在當前i到j經過k點的路徑與直連的路徑中選最短matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);}}} }

其中，matrix為有n個點的圖的鄰接矩陣，若兩點沒有直連路徑則設相應的值為MAX。執行函數后的矩陣的對應項即為兩點最短距離

轉載于:https://www.cnblogs.com/Algorithm-X/p/7219784.html

總結

以上是生活随笔為你收集整理的两点之间最短路径：弗洛伊德算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。