waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          來源:http://blog.chinaunix.net/u1/50399/showart_405608.html

          標題:Single-Source Shortest Paths (Dijkstra's algorithm)
          輸入:n個頂點的有向帶權圖G,表述為n*n矩陣。
                起始點:v0 其取值范圍為0~n-1。
          輸出:最短路徑及其長度,表述為一個二維數組path[n-1][3],每個數組元素由三個數據項組成,其中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]==&& 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]==&& 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;
              }
          }

           

          輸出結果:
          源點:0; 終點:2; 長度:10; 終點前趨:-1
          源點:0; 終點:4; 長度:30; 終點前趨:-1
          源點:0; 終點:3; 長度:50; 終點前趨:1
          源點:0; 終點:5; 長度:60; 終點前趨:2

          posted on 2009-04-15 22:19 weesun一米陽光 閱讀(777) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 饶河县| 文成县| 东光县| 读书| 临清市| 交城县| 临海市| 万载县| 益阳市| 扬州市| 定远县| 玉屏| 东兴市| 宁阳县| 长乐市| 林芝县| 泰兴市| 高台县| 七台河市| 微博| 泰安市| 壤塘县| 博客| 赣榆县| 仁怀市| 阿拉尔市| 北安市| 剑阁县| 彝良县| 台湾省| 昌平区| 家居| 土默特右旗| 荃湾区| 太原市| 馆陶县| SHOW| 宁南县| 湄潭县| 新昌县| 浑源县|