waysun一路陽光

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

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

          標(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]==&& 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;
              }
          }

           

          輸出結(jié)果:
          源點: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源碼總結(jié)備用
          主站蜘蛛池模板: 长泰县| 安龙县| 无棣县| 徐汇区| 西吉县| 阿拉尔市| 新干县| 涪陵区| 申扎县| 卢湾区| 泽库县| 长葛市| 东方市| 大悟县| 保定市| 郴州市| 中超| 瑞丽市| 宁安市| 青川县| 漳州市| 若尔盖县| 宁南县| 昔阳县| 新野县| 祥云县| 景宁| 历史| 哈密市| 岐山县| 屏边| 花莲市| 景谷| 平武县| 青神县| 阳江市| 梧州市| 南昌市| 寻甸| 平武县| 盐山县|