posts - 241,  comments - 116,  trackbacks - 0
          暑假寫的Java實現(xiàn)Dijkstra單源最短路徑,主要特點是以起始點為中心向外層層擴展,直到擴展到終點為止。描述就不寫了,看相關書籍吧。 Dijkstra是一個貪心算法。
          package Section9;


          /*第九章  貪婪算法   Dijkstra單源最短路徑*/

          public class Dijkstra {

              /**
          墻頭草

               * @param args
               */
              public static void main(String[] args) {
                  // TODO Auto-generated method stub
                  int[][] weight = {
                          {0,3,2000,7,9999999},
                          {3,0,4,2,9999999},
                          {9999999,4,0,5,6},
                          {7,2,5,0,4},
                          {9999999,9999999,4,6,0}
                  };
                  
                  int[] path = Dijsktra(weight,0);
                  for(int i = 0;i < path.length;i++)
                      System.out.print(path[i] + "  ");
              }
              

              public static int[] Dijsktra(int[][] weight,int start){
                  //接受一個有向圖的權重矩陣,和一個起點編號start(從0編號,頂點存在數(shù)組中)
                  //返回一個int[] 數(shù)組,表示從start到它的最短路徑長度
                  int n = weight.length;        //頂點個數(shù)
                  int[] shortPath = new int[n];    //存放從start到其他各點的最短路徑
                  int[] visited = new int[n];        //標記當前該頂點的最短路徑是否已經(jīng)求出,1表示已求出
                  
                  //初始化,第一個頂點求出
                  shortPath[start] = 0;
                  visited[start] = 1;
                  
                  for(int count = 1;count <= n - 1;count++)        //要加入n-1個頂點
                  {
                      int k = -1;    //選出一個距離初始頂點start最近的未標記頂點
                      int dmin = 1000;
                      for(int i = 0;i < n;i++)
                      {
                          if(visited[i] == 0 && weight[start][i] < dmin)
                          {
                              dmin = weight[start][i];
                              k = i;
                          }    
                      }
                      
                      //將新選出的頂點標記為已求出最短路徑,且到start的最短路徑就是dmin
                      shortPath[k] = dmin;
                      visited[k] = 1;
                      
                      //以k為中間點想,修正從start到未訪問各點的距離
                      for(int i = 0;i < n;i++)
                      {
                          if(visited[i] == 0 && weight[start][k] + weight[k][i] < weight[start][i])
                               weight[start][i] = weight[start][k] + weight[k][i];
                      }    
              
                  }
                  
                  return shortPath;
              }
          }
          posted on 2011-10-09 10:52 墻頭草 閱讀(3501) 評論(0)  編輯  收藏

          只有注冊用戶登錄后才能發(fā)表評論。


          網(wǎng)站導航:
           
          人人游戲網(wǎng) 軟件開發(fā)網(wǎng) 貨運專家
          主站蜘蛛池模板: 泰安市| 灌阳县| 黄大仙区| 江油市| 元朗区| 乌审旗| 永登县| 景德镇市| 沙河市| 肥城市| 禹城市| 水富县| 喀什市| 宜兰市| 绥化市| 长沙县| 工布江达县| 丽水市| 桦南县| 奉化市| 白山市| 英超| 墨玉县| 泸西县| 神农架林区| 尤溪县| 延寿县| 白朗县| 通山县| 藁城市| 资源县| 临猗县| 开平市| 磴口县| 安顺市| 麦盖提县| 池州市| 乐安县| 龙门县| 麟游县| 清涧县|