/*//1、確定數據結構, mapf[i][j] 為點i到點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、如果源點為1，則 s = {1}, 則 v-s = {2,3,4,5}; s為已經規劃好的點,v-s是需要規劃的點     var dist = []; //dist[i] = mapf[1][i];dist[1] = 0;    //源點1到i有邊相連，初始化前驅為1（源點為前驅），否則初始化為-1    var p = [-1,1,1,-1,-1];              //3、找到 v-s = {2，3，4，5}集合里面,到源點1，最近的點      //得出結果為2，節點為 t = 2，則 v-s={3、4、5}，s={1、2}；           //4、借道t=2，所有t的相鄰點，借道t；例如相鄰點3,則 a = dist[2] + maf[2][3]; b = dist[3];    //兩個取較小值，得a < b; 2-3為捷徑，則記錄下dist[3] = a;記錄下3的前驅點 p[3] = 2;    //經過第4步，計算了2的相鄰點，3、4；         //5、比較v-s={3、4、5}的到源點的最近距離，即是 v-s={3、4、5}時，執行第3步，此時相當于源點為2會再次得出最小 t         //6、重復 3、4、5步*/                   function Dijkstra(){       //初始化構造一個集合，mapt[i][j]為點i到j的距離,不通的為無窮大      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;      //開始計算      this.dijkstra = function(u){ //u為源點        var dist = []; //dist[i]為點i到y的最短距離        var p = [];  //p[i] 為點i的前溯點        var flag = []; //flag[i] 是否已經加入 s集合               //初始化數據 dist,p,flag        for(var i = 1; i <= n; i++){          dist[i] = mapt[u][i]; //從源點到i的距離           if(dist[i] == Infinity){ //前溯點如果不通過為-1            p[i] = -1;          }else{            p[i] = u;          }                     flag[i] = false; //都沒有選中        }                 flag[u] = true; //選擇了源點，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為捷徑點(t為前溯點)，尋找所有滿足條件的點            if(!flag[k] && mapt[t][k] < Infinity ){              if(dist[k] > (dist[t] + mapt[t][k])){                dist[k] = dist[t] + mapt[t][k]; //源點到k的距離 > 源點到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));