js中圖數(shù)據(jù)結(jié)構(gòu)處理迪杰斯特拉算法的示例分析

小編給大家分享一下js中圖數(shù)據(jù)結(jié)構(gòu)處理迪杰斯特拉算法的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

/*//1、確定數(shù)據(jù)結(jié)構(gòu), 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為已經(jīng)規(guī)劃好的點,v-s是需要規(guī)劃的點 
    var dist = []; //dist[i] = mapf[1][i];dist[1] = 0;
    //源點1到i有邊相連，初始化前驅(qū)為1（源點為前驅(qū)），否則初始化為-1
    var p = [-1,1,1,-1,-1];
     
     
    //3、找到 v-s = {2，3，4，5}集合里面,到源點1，最近的點
      //得出結(jié)果為2，節(jié)點為 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的前驅(qū)點 p[3] = 2;
    //經(jīng)過第4步，計算了2的相鄰點，3、4；
     
    //5、比較v-s={3、4、5}的到源點的最近距離，即是 v-s={3、4、5}時，執(zhí)行第3步，此時相當(dāng)于源點為2會再次得出最小 t
     
    //6、重復(fù) 3、4、5步*/
     
     
     
    function Dijkstra(){
       //初始化構(gòu)造一個集合，mapt[i][j]為點i到j(luò)的距離,不通的為無窮大
      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(tǒng)的最短距離
        var p = [];  //p[i] 為點i的前溯點
        var flag = []; //flag[i] 是否已經(jīng)加入 s集合
       
        //初始化數(shù)據(jù) 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));

以上是“js中圖數(shù)據(jù)結(jié)構(gòu)處理迪杰斯特拉算法的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！