mramine364

Dijkstra - Fibonacci Heap Implementation

Jul 31st, 2016
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. Fibonacci heap object
  3. */
  4. function fh(){
  5.     return {
  6.         lt: [], // trees
  7.         minh: null, // node
  8.         iminh: -1,
  9.         isEmpty: function(){ return this.lt.length==0; },
  10.         add: function(n){
  11.             this.lt.push(n);
  12.             if( this.minh==null || this.minh.v>n.v ){
  13.                 this.minh = n;
  14.                 this.iminh = this.lt.length-1;
  15.             }
  16.         },
  17.         removeMin: function(){
  18.             if( this.minh==null ){
  19.                 console.log(null)
  20.             }
  21.             let tm = this.minh;
  22.             this.lt.splice(this.iminh,1);
  23.  
  24.             for(let i=0;i<this.minh.childs.length;i++){
  25.                 this.lt.push(this.minh.childs[i]);
  26.             }          
  27.             let nlt = this.lt; this.lt = [];
  28.             for(let i=0;i<nlt.length;i++){
  29.                 this.merge(nlt[i]);
  30.             }
  31.             this.setMin();
  32.             return tm;
  33.         },
  34.         setMin: function(){
  35.             if( this.lt.length==0 ){
  36.                 this.minh = null;
  37.                 this.iminh = 0;
  38.                 return;
  39.             }
  40.             this.minh = this.lt[0];
  41.             this.iminh = 0;
  42.             for(let i=1;i<this.lt.length;i++){
  43.                 if( this.lt[i].v<this.minh.v ){
  44.                     this.minh = this.lt[i];
  45.                     this.iminh = i;
  46.                 }
  47.             }          
  48.         },
  49.         merge: function(n){
  50.             if( this.lt.length==0 ){
  51.                 this.lt.push(n);
  52.                 return;
  53.             }
  54.             let i=0;
  55.             while( i<this.lt.length && n.deg>this.lt[i].deg )
  56.                 i++;
  57.             if( n.deg==this.lt[i].deg ){
  58.                 if( this.lt[i].v<n.v ){
  59.                     this.lt[i].add(n);
  60.                     let tp,t;
  61.                     while( i+1<this.lt.length &&
  62.                         (t=this.lt[i+1]).deg==(tp=this.lt[i]).deg ){
  63.                         if( tp.v<t.v ){
  64.                             tp.add(t);
  65.                             this.lt.splice(i+1,1);
  66.                         }else{
  67.                             t.add(tp);
  68.                             this.lt.splice(i,1);
  69.                         }
  70.                     }
  71.                 }else{
  72.                     n.add(this.lt.splice(i,1)[0]);
  73.                     this.merge(n);
  74.                 }
  75.             }else{
  76.                 this.lt.splice(i,0,n);
  77.             }
  78.         },
  79.         build: function(arr){
  80.             for(let i=0;i<arr.length;i++){
  81.                 let n = fh_node(arr[i], 0);
  82.                 this.add(n);
  83.             }
  84.             console.log(this)
  85.         }
  86.     };
  87. }
  88.  
  89. /**
  90. Dijkstra
  91. */
  92. function dijkstra_vertice(n) {
  93.     return {
  94.         par: null,
  95.         d: Infinity,
  96.         n: n,
  97.         succ: [], // edges
  98.         close: false,
  99.         // fibo heap
  100.         v: this.d,
  101.         childs: [],
  102.         deg: 0,
  103.         add: function(n){
  104.             this.childs.push(n);
  105.             this.deg++;
  106.         }
  107.     };
  108. }
  109.  
  110. function dijkstra_egde(f,t,w){
  111.     return {
  112.         f: f,
  113.         t: t,
  114.         w: w
  115.     };
  116. }
  117.  
  118. let V=[], E=[];
  119. let s=dijkstra_vertice("s"); V.push(s); s.d=s.v=0;
  120. let u=dijkstra_vertice("u"); V.push(u);
  121. let x=dijkstra_vertice("x"); V.push(x);
  122. let v=dijkstra_vertice("v"); V.push(v);
  123. let y=dijkstra_vertice("y"); V.push(y);
  124. let su=dijkstra_egde(s,u,10); E.push(su);
  125. let sx=dijkstra_egde(s,x,5); E.push(sx);
  126. let ux=dijkstra_egde(u,x,2); E.push(ux);
  127. let xu=dijkstra_egde(x,u,3); E.push(xu);
  128. let uv=dijkstra_egde(u,v,1); E.push(uv);
  129. let xy=dijkstra_egde(x,y,2); E.push(xy);
  130. let xv=dijkstra_egde(x,v,9); E.push(xv);
  131. let vy=dijkstra_egde(v,y,4); E.push(vy);
  132. let yv=dijkstra_egde(y,v,6); E.push(yv);
  133. let ys=dijkstra_egde(y,s,7); E.push(ys);
  134. s.succ.splice(0,0,su,sx);
  135. u.succ.splice(0,0,ux,uv);
  136. x.succ.splice(0,0,xu,xv,xy);
  137. v.succ.splice(0,0,vy);
  138. y.succ.splice(0,0,ys,yv);
  139.  
  140. let dijkstra = {
  141.     app2: function(v, e){ // apply dijkstra with fibonacci heap
  142.         let vs = fh();
  143.         vs.add(v[0]); // add initiale vertice
  144.         v[0].close = true;
  145.         while( !vs.isEmpty() ){
  146.             let ve = vs.removeMin();
  147.             for(let i=0;i<ve.succ.length;i++){
  148.                 if( ve.succ[i].t.d>ve.d+ve.succ[i].w ){
  149.                     ve.succ[i].t.d=ve.d+ve.succ[i].w;
  150.                     ve.succ[i].t.v=ve.d+ve.succ[i].w;
  151.                     ve.succ[i].t.par = ve;
  152.                     if( !ve.succ[i].t.close ){
  153.                         vs.add(ve.succ[i].t);
  154.                         ve.succ[i].t.close = true;
  155.                     }
  156.                 }
  157.             }
  158.         }
  159.     }
  160. };
Advertisement
Add Comment
Please, Sign In to add comment