Floyed算法

原理：

Floyed-Warshall 算法用來找出每對點之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。

點 i 到點 j 的距離 ：distance(i,j)

點i 到點 k 的距離加上點 k 到點 j 的距離：distance(i,k) + distance(k,j)

如果distance(i,j) < distance(i,k) + distance(k,j)，那么就更新點 i 到點 j 的距離為distance(i,k) + distance(k,j)，同時記錄下點k,因為k是點i到點j的最短路徑的中的轉折點

五行主函數：

public static void floyed(int[][] map){for(int k = 0;k<length;k++){for(int i = 0;i<length;i++){for(int j = 0;j<length;j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j] = map[i][k]+map[k][j];}}}}}

沒錯 時間復雜度為O(n^3)~~;

實際用例

import java.util.ArrayList;public class Floyed {public static void start(int[][] map,ArrayList[][] path){int length = map.length;for(int k = 0;k<length;k++){for(int i = 0;i<length;i++){for(int j = 0;j<length;j++){if(map[i][j]>map[i][k]+map[k][j]){map[i][j] = map[i][k]+map[k][j];path[i][j].add(k);}}}}}public static void main(String[] args) {int[][] map = new int[5][5];for(int i = 0;i<map.length;i++){for(int j = 0;j<map[i].length;j++){map[i][j] = (i==j)? 0 : 1000;}}map[0][1] = 3;map[1][2] = 8;map[0][4] = -4;map[1][3] = 1;map[1][4] = 7;map[2][1] = 4;map[3][0] = 2;map[3][2] = -5;map[4][3] = 6;ArrayList<Integer>[][] path = new ArrayList[5][5];for(int i = 0;i<path.length;i++){for (int j = 0;j<path[i].length;j++){path[i][j] = new ArrayList<>();}}Floyed.start(map,path);for(int i = 0;i<path.length;i++) {for (int j = 0; j < path[i].length; j++) {System.out.print(i + "到" + j+ "路徑："+i+"->");for (int z : path[i][j]) {System.out.print(z + "->");}System.out.println(j+" 距離為"+map[i][j]);}System.out.println();}}}

結果

0到0路徑：0->0 距離為0
0到1路徑：0->4->1 距離為1
0到2路徑：0->1->3->4->2 距離為-3
0到3路徑：0->1->4->3 距離為2
0到4路徑：0->4 距離為-4

1到0路徑：1->3->0 距離為3
1到1路徑：1->1 距離為0
1到2路徑：1->3->2 距離為-4
1到3路徑：1->3 距離為1
1到4路徑：1->3->4 距離為-1

2到0路徑：2->3->0 距離為7
2到1路徑：2->1 距離為4
2到2路徑：2->2 距離為0
2到3路徑：2->1->3 距離為5
2到4路徑：2->0->1->3->4 距離為3

3到0路徑：3->0 距離為2
3到1路徑：3->0->2->1 距離為-1
3到2路徑：3->2 距離為-5
3到3路徑：3->3 距離為0
3到4路徑：3->0->4 距離為-2

4到0路徑：4->3->0 距離為8
4到1路徑：4->3->1 距離為5
4到2路徑：4->3->2 距離為1
4到3路徑：4->3 距離為6
4到4路徑：4->4 距離為0

---

你可能還敢興趣的圖論算法(均附Java實現代碼)：

• 你必須會的–Dijkstra算法–單源最短路徑問題

• 你必須會的DFS的遞歸實現與堆棧實現

• 你了解歐拉回路嗎？

• 你必須會的啟發式搜索算法–A*算法

總結

以上是生活随笔為你收集整理的算法实验--主函数只有五行的Floyed的算法以及最短路径输出的全部內容，希望文章能夠幫你解決所遇到的問題。

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