waysun一路陽光

標(biāo)題：Single-Source Shortest Paths (Dijkstra's algorithm)
輸入：n個頂點的有向帶權(quán)圖G，表述為n*n矩陣。
      起始點:v0 其取值范圍為0~n-1。
輸出：最短路徑及其長度，表述為一個二維數(shù)組path[n-1][3]，每個數(shù)組元素由三個數(shù)據(jù)項組成，其中path[i][0]代表此最短路徑之終點，path[i][1]代表此最短路徑之長度，path[i][2]代表此最短路徑終點之前趨。

public class ShortestPathTest
{ 
   static int[][] graph={
       {1000, 1000, 10 , 1000, 30 , 100 ,},
       {1000, 1000, 5 , 1000, 1000, 1000,},
       {1000, 1000, 1000, 50 , 1000, 1000,},
       {1000, 1000, 1000, 1000, 1000, 10 ,},
       {1000, 1000, 1000, 20 , 1000, 60 ,},
       {1000, 1000, 1000, 1000, 1000, 1000,},
   };
   static int [][] path;
   static int v=0;

   public static void main(String[] args)
   {
       ShortestPath sortestPath=new ShortestPath();
       sortestPath.input(graph, v);
       path=sortestPath.getPath();
       for(int i=0; path[i][1]!=1000; i++){
           System.out.println("源點：" + v + "; 終點：" + path[i][0] + 
           "; 長度：" + path[i][1] + "; 終點前趨：" + path[i][2]);
       }
   }
}

class ShortestPath
{
    private int[][] graph;
    private int v;
    private int[][] path;
    
    void input(int[][] graph, int v)
    {
        this.graph=graph;
        this.v=v;
        calculate();
    }
    
    void calculate()
    {
        path=new int[graph.length-1][];
        int[] s=new int[graph.length];
        for(int i : s)i=0; s[v]=2;
        
        //按路徑值從小到大的順序求解各條最短路徑

        for(int i=0; i<graph.length-1; i++){
            //求v到集合s2的最短路徑pointToSet[0]

            int[][] pointToSet={{1, 1000, -1,},{1, 1000, -1,},};
            for(int j=0; j<graph.length; j++){
                if(s[j]==0 && graph[v][j]<pointToSet[0][1]){
                    pointToSet[0][1]=graph[v][j];
                    pointToSet[0][0]=j;
                }
            }
            
            //求集合s1到集合s2的最短路徑setToSet[0]

            int[][] setToSet={{1, 1000, -1,},};
            for(int j=0; j<i; j++){
                //求頂點path[j][0]到點集s2的最短路徑pointToSet[1]

                pointToSet[1][1]=1000; pointToSet[1][2]=j;
                for(int k=0; k<graph.length; k++){
                   if(s[k]==0 && graph[path[j][0]][k]<pointToSet[1][1]){
                        pointToSet[1][1]=graph[path[j][0]][k];
                        pointToSet[1][0]=k;
                    }
                }
                pointToSet[1][1]=pointToSet[1][1]+path[j][1];
                if(pointToSet[1][1]<setToSet[0][1]){
                    setToSet[0]=pointToSet[1];
                }
            }
            
            //比較pointToSet[0]及setToSet[0]，求其小者，作為path[i]之值

            if(pointToSet[0][1]<setToSet[0][1])
                path[i]=pointToSet[0];
            else
                path[i]=setToSet[0];
                
            s[path[i][0]]=1; //把頂點劃為已求最短路終點之點集

        }
    }

    int[][] getPath()
    {
        return path;
    }
}