Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /**
- Fibonacci heap object
- */
- function fh(){
- return {
- lt: [], // trees
- minh: null, // node
- iminh: -1,
- isEmpty: function(){ return this.lt.length==0; },
- add: function(n){
- this.lt.push(n);
- if( this.minh==null || this.minh.v>n.v ){
- this.minh = n;
- this.iminh = this.lt.length-1;
- }
- },
- removeMin: function(){
- if( this.minh==null ){
- console.log(null)
- }
- let tm = this.minh;
- this.lt.splice(this.iminh,1);
- for(let i=0;i<this.minh.childs.length;i++){
- this.lt.push(this.minh.childs[i]);
- }
- let nlt = this.lt; this.lt = [];
- for(let i=0;i<nlt.length;i++){
- this.merge(nlt[i]);
- }
- this.setMin();
- return tm;
- },
- setMin: function(){
- if( this.lt.length==0 ){
- this.minh = null;
- this.iminh = 0;
- return;
- }
- this.minh = this.lt[0];
- this.iminh = 0;
- for(let i=1;i<this.lt.length;i++){
- if( this.lt[i].v<this.minh.v ){
- this.minh = this.lt[i];
- this.iminh = i;
- }
- }
- },
- merge: function(n){
- if( this.lt.length==0 ){
- this.lt.push(n);
- return;
- }
- let i=0;
- while( i<this.lt.length && n.deg>this.lt[i].deg )
- i++;
- if( n.deg==this.lt[i].deg ){
- if( this.lt[i].v<n.v ){
- this.lt[i].add(n);
- let tp,t;
- while( i+1<this.lt.length &&
- (t=this.lt[i+1]).deg==(tp=this.lt[i]).deg ){
- if( tp.v<t.v ){
- tp.add(t);
- this.lt.splice(i+1,1);
- }else{
- t.add(tp);
- this.lt.splice(i,1);
- }
- }
- }else{
- n.add(this.lt.splice(i,1)[0]);
- this.merge(n);
- }
- }else{
- this.lt.splice(i,0,n);
- }
- },
- build: function(arr){
- for(let i=0;i<arr.length;i++){
- let n = fh_node(arr[i], 0);
- this.add(n);
- }
- console.log(this)
- }
- };
- }
- /**
- Dijkstra
- */
- function dijkstra_vertice(n) {
- return {
- par: null,
- d: Infinity,
- n: n,
- succ: [], // edges
- close: false,
- // fibo heap
- v: this.d,
- childs: [],
- deg: 0,
- add: function(n){
- this.childs.push(n);
- this.deg++;
- }
- };
- }
- function dijkstra_egde(f,t,w){
- return {
- f: f,
- t: t,
- w: w
- };
- }
- let V=[], E=[];
- let s=dijkstra_vertice("s"); V.push(s); s.d=s.v=0;
- let u=dijkstra_vertice("u"); V.push(u);
- let x=dijkstra_vertice("x"); V.push(x);
- let v=dijkstra_vertice("v"); V.push(v);
- let y=dijkstra_vertice("y"); V.push(y);
- let su=dijkstra_egde(s,u,10); E.push(su);
- let sx=dijkstra_egde(s,x,5); E.push(sx);
- let ux=dijkstra_egde(u,x,2); E.push(ux);
- let xu=dijkstra_egde(x,u,3); E.push(xu);
- let uv=dijkstra_egde(u,v,1); E.push(uv);
- let xy=dijkstra_egde(x,y,2); E.push(xy);
- let xv=dijkstra_egde(x,v,9); E.push(xv);
- let vy=dijkstra_egde(v,y,4); E.push(vy);
- let yv=dijkstra_egde(y,v,6); E.push(yv);
- let ys=dijkstra_egde(y,s,7); E.push(ys);
- s.succ.splice(0,0,su,sx);
- u.succ.splice(0,0,ux,uv);
- x.succ.splice(0,0,xu,xv,xy);
- v.succ.splice(0,0,vy);
- y.succ.splice(0,0,ys,yv);
- let dijkstra = {
- app2: function(v, e){ // apply dijkstra with fibonacci heap
- let vs = fh();
- vs.add(v[0]); // add initiale vertice
- v[0].close = true;
- while( !vs.isEmpty() ){
- let ve = vs.removeMin();
- for(let i=0;i<ve.succ.length;i++){
- if( ve.succ[i].t.d>ve.d+ve.succ[i].w ){
- ve.succ[i].t.d=ve.d+ve.succ[i].w;
- ve.succ[i].t.v=ve.d+ve.succ[i].w;
- ve.succ[i].t.par = ve;
- if( !ve.succ[i].t.close ){
- vs.add(ve.succ[i].t);
- ve.succ[i].t.close = true;
- }
- }
- }
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment