| 1234567891011121314 |
- var r,t={exports:{}};function e(){return r?t.exports:(r=1,t.exports=e={single_source_shortest_paths:function(r,t,o){var s={},u={};u[t]=0;var n,i,a,h,p,f,c,_=e.PriorityQueue.make();for(_.push(t,0);!_.empty();)for(a in i=(n=_.pop()).value,h=n.cost,p=r[i]||{})p.hasOwnProperty(a)&&(f=h+p[a],c=u[a],(void 0===u[a]||c>f)&&(u[a]=f,_.push(a,f),s[a]=i));if(void 0!==o&&void 0===u[o]){var v=["Could not find a path from ",t," to ",o,"."].join("");throw new Error(v)}return s},extract_shortest_path_from_predecessor_list:function(r,t){for(var e=[],o=t;o;)e.push(o),r[o],o=r[o];return e.reverse(),e},find_path:function(r,t,o){var s=e.single_source_shortest_paths(r,t,o);return e.extract_shortest_path_from_predecessor_list(s,o)},
- /**
- * A very naive priority queue implementation.
- */
- PriorityQueue:{make:function(r){var t,o=e.PriorityQueue,s={};for(t in r=r||{},o)o.hasOwnProperty(t)&&(s[t]=o[t]);return s.queue=[],s.sorter=r.sorter||o.default_sorter,s},default_sorter:function(r,t){return r.cost-t.cost},
- /**
- * Add a new item to the queue and ensure the highest priority element
- * is at the front of the queue.
- */
- push:function(r,t){var e={value:r,cost:t};this.queue.push(e),this.queue.sort(this.sorter)},
- /**
- * Return the highest priority element in the queue.
- */
- pop:function(){return this.queue.shift()},empty:function(){return 0===this.queue.length}}});var e}export{e as r};
|
