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一米陽光 閱讀(782) 評論(0)  編輯  收藏 所屬分類: JAVA源碼 、總結備用
          主站蜘蛛池模板: 淮安市| 景泰县| 紫阳县| 虹口区| 平和县| 陵水| 迁安市| 昌都县| 镶黄旗| 常山县| 台前县| 报价| 青海省| 永春县| 西丰县| 淮滨县| 莱州市| 南丰县| 平顺县| 大理市| 呈贡县| 广宁县| 安乡县| 德钦县| 湖口县| 新邵县| 土默特右旗| 上犹县| 周至县| 革吉县| 朝阳县| 永顺县| 台中县| 冕宁县| 江西省| 和静县| 大丰市| 将乐县| 长乐市| 高唐县| 汉川市|