(Java) 尋求最短路徑 -- Floyd 公式運用

1. 
   
2. /* 
3.  *  
4.  * 尋求最短路徑 
5.  *  
6.  */  
7. public class ShortPath {  
8.   
9.     public static void main(String[] args) {  
10.           
11.          int[][] am = {{1,2,10},{2,3,20},{2,4,25},{3,5,18}  
12.                                ,{4,5,22},{4,6,95},{5,6,77}};//每個邊  
13.         /* Dijkstra d = new Dijkstra(am,7);  
14.          d.MatrixPrint(); 
15.          System.out.println("Dijkstra 頂點 1 至 個頂點最小距離 : "); 
16.          d.shortestPath(1); 
17.          System.out.println("Dijkstra 頂點 2 至 個頂點最小距離 : "); 
18.          d.shortestPath(2); 
19.          System.out.println("Dijkstra 頂點 3 至 個頂點最小距離 : "); 
20.          d.shortestPath(3); 
21.          System.out.println("Dijkstra 頂點 4 至 個頂點最小距離 : "); 
22.          d.shortestPath(4);*/  
23.          //"Floyd 方法 : "  
24.          System.out.println("Floyd 方法 : ");  
25.          new Floyd(am,7).PrintList(); ;  
26.     }  
27.   
28. }  
29. class Floyd extends Adjacency{  //Adjacency 請觀看 Dijkstra文章
30. int[][] A ;  
31. int[][] a ;  
32. int k  = 1;//為次方  
33.     Floyd(int[][] M, int n) {  
34.         super(M, n);  
35.         //Copy 矩陣  
36.         A = Arrays.copyOf(Matrix, Matrix.length);  
37.     }  
38.     int min(int A , int A1){  
39.         return A<A1? A : A1 ; //最小值為最短距離  
40.     }  
41.     int A(int k , int i , int j){  //取出矩陣值  
42.         int value  = A[i][j] ;  
43.         return value;  
44.     }  
45.     void Floyd(){  
46.         a = new int[A.length][A.length];          
47.         for(int r = 1 ; r < A.length; r++)  
48.             for(int c = 1 ; c < A.length; c++)  
49.                 a[r][c] =  min(A(k-1, r , c), A(k-1, r , k) + A(k-1, k , c)) ;//  A^k[i][j] = min(A^k-1[i][j] , A^k-1[j][k]+A^k-1[k][j);  
50.         A = a ;//將a的刺件交給A      
51.         if(k == A.length-1) return ;  
52.         k++ ;    
53.         Floyd() ;  
54.     }  
55.     void PrintList(){  
56.         Floyd();  
57.         for(int r = 1 ; r < A.length; r++){  
58.             for(int c = 1 ; c < A.length; c++){  
59.                 System.out.print(r+" to "+c+" 最短距離 : ");  
60.                 if(A[r][c] == 999)  
61.                     System.out.println("∞"+"  ");  
62.                 else  
63.                     System.out.println(A[r][c]+"  ");  
64.             }  
65.             System.out.println();  
66.         }  
67.     }  
68.       
69. }