/*//1、確定數(shù)據(jù)結(jié)構(gòu), mapf[i][j] 為點(diǎn)i到點(diǎn)j的距離
    [
      Infinity  2     5  Infinity Infinity
      Infinity Infinity   2    6  Infinity
      Infinity Infinity Infinity   7    1
      Infinity Infinity   2  Infinity   4
      Infinity Infinity Infinity Infinity Infinity
    ];
     
     
    //2、如果源點(diǎn)為1，則 s = {1}, 則 v-s = {2,3,4,5}; s為已經(jīng)規(guī)劃好的點(diǎn),v-s是需要規(guī)劃的點(diǎn) 
    var dist = []; //dist[i] = mapf[1][i];dist[1] = 0;
    //源點(diǎn)1到i有邊相連，初始化前驅(qū)為1（源點(diǎn)為前驅(qū)），否則初始化為-1
    var p = [-1,1,1,-1,-1];
     
     
    //3、找到 v-s = {2，3，4，5}集合里面,到源點(diǎn)1，最近的點(diǎn)
      //得出結(jié)果為2，節(jié)點(diǎn)為 t = 2，則 v-s={3、4、5}，s={1、2}；
       
    //4、借道t=2，所有t的相鄰點(diǎn)，借道t；例如相鄰點(diǎn)3,則 a = dist[2] + maf[2][3]; b = dist[3];
    //兩個(gè)取較小值，得a < b; 2-3為捷徑，則記錄下dist[3] = a;記錄下3的前驅(qū)點(diǎn) p[3] = 2;
    //經(jīng)過(guò)第4步，計(jì)算了2的相鄰點(diǎn)，3、4；
     
    //5、比較v-s={3、4、5}的到源點(diǎn)的最近距離，即是 v-s={3、4、5}時(shí)，執(zhí)行第3步，此時(shí)相當(dāng)于源點(diǎn)為2會(huì)再次得出最小 t
     
    //6、重復(fù) 3、4、5步*/
     
     
     
    function Dijkstra(){
       //初始化構(gòu)造一個(gè)集合，mapt[i][j]為點(diǎn)i到j(luò)的距離,不通的為無(wú)窮大
      var mapt = [
        [undefined,undefined,undefined,undefined,undefined,undefined],
        [undefined,Infinity,2,5,Infinity,Infinity],
        [undefined,Infinity,Infinity,2,6,Infinity],
        [undefined,Infinity,Infinity,Infinity,7,1],
        [undefined,Infinity,Infinity,2,Infinity,4],
        [undefined,Infinity,Infinity,Infinity,Infinity,Infinity],
      ];
       
      var n = mapt.length - 1;
      //開始計(jì)算
      this.dijkstra = function(u){ //u為源點(diǎn)
        var dist = []; //dist[i]為點(diǎn)i到y(tǒng)的最短距離
        var p = [];  //p[i] 為點(diǎn)i的前溯點(diǎn)
        var flag = []; //flag[i] 是否已經(jīng)加入 s集合
       
        //初始化數(shù)據(jù) dist,p,flag
        for(var i = 1; i <= n; i++){
          dist[i] = mapt[u][i]; //從源點(diǎn)到i的距離 
          if(dist[i] == Infinity){ //前溯點(diǎn)如果不通過(guò)為-1
            p[i] = -1;
          }else{
            p[i] = u;
          }
           
          flag[i] = false; //都沒(méi)有選中
        }
         
        flag[u] = true; //選擇了源點(diǎn)，s集合只有 u
 
        for(var i = 1; i <= n; i++){
          var t = u; var temp = Infinity;  
          for(var j = 1; j <= n ; j++){ //獲取dist里面，v-s集合的最短距離
            if(!flag[j] && dist[j] <= temp){
              temp = dist[j];
              t = j;
            }
          }
           
          //查看是否找到最短的距離
          if(t == u){
            return {
              dist:dist,
              p:p
            }; 
          }
           
          //找到了,將t加入集合 s
          flag[t] = true;
           
          for(var k = 1 ; k <= n; k++){ //以t為捷徑點(diǎn)(t為前溯點(diǎn))，尋找所有滿足條件的點(diǎn)
            if(!flag[k] && mapt[t][k] < Infinity ){
              if(dist[k] > (dist[t] + mapt[t][k])){
                dist[k] = dist[t] + mapt[t][k]; //源點(diǎn)到k的距離 > 源點(diǎn)到t的距離 + t到k的距離
                p[k] = t;
              }
            }
          }
        }
         
        return {
          dist:dist,
          p:p
        }
 
      }
       
      this.getpath = function(u){
        var process = this.dijkstra(u);
        var dist = process.dist;
        var p = process.p;
        for(var i = 1; i <= n; i++){
          var start = i;
          var str = i;
          while(start != -1){
            start = p[start]; //迭代出路徑
            if(start != -1){
              str = str + '、' + start;
            }
          }
          console.log(str);
        }
      }
       
    }     
    var Dijk = new Dijkstra();
    //console.log(Dijk.dijkstra(1));
    console.log(Dijk.getpath(1));