算法實驗--主函數隻有五行的Floyed的算法以及最短路徑輸出

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

• ​​你必須會的–Dijkstra算法–單源最短路徑問題​​
• ​​你必須會的DFS的遞歸實作與堆棧實作​​
• ​​你了解歐拉回路嗎？​​
• ​​你必須會的啟發式搜尋算法–A*算法​​