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

    

1. /* 
2.  *  
3.  * 尋求最短路徑 
4.  *  
5.  */  
6. public class ShortPath {  
7.   
8.     public static void main(String[] args) {  
9.          int[][] am = {{1,2,10},{2,3,20},{2,4,25},{3,5,18}  
10.                                ,{4,5,22},{4,6,95},{5,6,77}};//每個邊  
11.          Dijkstra d = new Dijkstra(am , 7);  
12.          System.out.println("相鄰矩陣 : ");  
13.          d.MatrixPrint();  
14.          System.out.println("Dijkstra 頂點 1 至 個頂點最小距離 : ");  
15.          d.shortestPath(1);  
16.          System.out.println("Dijkstra 頂點 2 至 個頂點最小距離 : ");  
17.          d.shortestPath(2);  
18.          System.out.println("Dijkstra 頂點 3 至 個頂點最小距離 : ");  
19.          d.shortestPath(3);  
20.          System.out.println("Dijkstra 頂點 4 至 個頂點最小距離 : ");  
21.          d.shortestPath(4);  
22.     }  
23.   
24. }  
25. class Dijkstra extends Adjacency{  
26.     int[] S ;//頂點集合  
27.     int[] D ; //距離集合  
28.     Dijkstra(int[][] M, int n) {  
29.         super(M , n ) ;  
30.         S = new int[n];  
31.         D = new int[n];  
32.     }  
33.     void shortestPath(int vext){          
34.         int shortv = 1;  
35.         for(int i = 1 ; i < Matrix.length ; i++)  
36.             D[i] = Matrix[vext][i] ; //D[i]為 vext 到 i 的距離  
37.         S[vext] = 1 ; //加入起始頂點  
38.         for(int i = 1 ; i < Matrix.length ; i++){  
39.             int shortdistance  = 999;  
40.             for(int j = 1 ;  j < Matrix.length ; j++)  
41.                  if(D[j] < shortdistance && S[j] == 0 ){  //為最小且沒加入至S集合  
42.                      shortdistance = D[j] ;  
43.                      shortv = j ;  
44.                  }  
45.             S[shortv] = 1 ;//加入至S集合  
46.             for(int j = 1 ;  j < Matrix.length ; j++){  
47.                 if(S[j] == 0 && D[j] > D[shortv] + Matrix[shortv][j])   //假設未加入至S且與最短距離的頂點相鄰  
48.                     D[j] = D[shortv] + Matrix[shortv][j] ; //就把起始點到最短距離頂點相鄰點距離和加入至 D[j]  
49.             }  
50.               
51.         }  
52.         //印出  
53.         for(int i = 1 ; i < D.length ; i++)  
54.             if(D[i]  == 999)  
55.                 System.out.println(vext+"  to  "+i+"最短距離為 : ∞ " );  
56.             else  
57.             System.out.println(vext+"  to  "+i+"最短距離為 : "+D[i] );     
58.         //重製  
59.         S = new int[S.length];  
60.         D = new int[D.length];  
61.           
62.     }  
63.   
64. }  
65.   
66. abstract class  Adjacency{  //相鄰矩陣
67.     int[][] Matrix ;  
68.     int max = 999 ;  
69.      Adjacency(int[][] M , int n){  
70.         Matrix = new int[n][n] ;  
71.         for(int i = 1 ; i < n ; i++){  
72.             for(int j = 1 ; j < n ; j++){  
73.                  if(i == j) Matrix[i][j] = 0 ; //頂點相同代表沒距離  
74.                  else Matrix[i][j] = max ;//不是相鄰點頂給X  
75.             }     
76.         }  
77.         for(int i = 0 ; i < M.length ; i++)  
78.              Matrix[M[i][0]][M[i][1]] = M[i][2] ;  //付值給Matrix  
79.     }  
80.       void MatrixPrint(){//印出  
81.         for(int i = 1 ; i < Matrix.length ; i++){  
82.             for(int j = 1 ; j< Matrix.length ; j++ )  
83.                 if(Matrix[i][j] == max)  System.out.print( "X"+"  ");  
84.                 else  System.out.print(Matrix[i][j]+"  ");    
85.             System.out.println();  
86.         }  
87.           
88.     }  
89.       
90.       
91. }