123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165 |
- 'use strict';
- var dijkstra = {
- single_source_shortest_paths: function(graph, s, d) {
-
-
- var predecessors = {};
-
-
- var costs = {};
- costs[s] = 0;
-
-
-
-
- var open = dijkstra.PriorityQueue.make();
- open.push(s, 0);
- var closest,
- u, v,
- cost_of_s_to_u,
- adjacent_nodes,
- cost_of_e,
- cost_of_s_to_u_plus_cost_of_e,
- cost_of_s_to_v,
- first_visit;
- while (!open.empty()) {
-
-
- closest = open.pop();
- u = closest.value;
- cost_of_s_to_u = closest.cost;
-
- adjacent_nodes = graph[u] || {};
-
-
-
- for (v in adjacent_nodes) {
- if (adjacent_nodes.hasOwnProperty(v)) {
-
- cost_of_e = adjacent_nodes[v];
-
-
-
- cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;
-
-
-
-
- cost_of_s_to_v = costs[v];
- first_visit = (typeof costs[v] === 'undefined');
- if (first_visit || cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {
- costs[v] = cost_of_s_to_u_plus_cost_of_e;
- open.push(v, cost_of_s_to_u_plus_cost_of_e);
- predecessors[v] = u;
- }
- }
- }
- }
- if (typeof d !== 'undefined' && typeof costs[d] === 'undefined') {
- var msg = ['Could not find a path from ', s, ' to ', d, '.'].join('');
- throw new Error(msg);
- }
- return predecessors;
- },
- extract_shortest_path_from_predecessor_list: function(predecessors, d) {
- var nodes = [];
- var u = d;
- var predecessor;
- while (u) {
- nodes.push(u);
- predecessor = predecessors[u];
- u = predecessors[u];
- }
- nodes.reverse();
- return nodes;
- },
- find_path: function(graph, s, d) {
- var predecessors = dijkstra.single_source_shortest_paths(graph, s, d);
- return dijkstra.extract_shortest_path_from_predecessor_list(
- predecessors, d);
- },
-
- PriorityQueue: {
- make: function (opts) {
- var T = dijkstra.PriorityQueue,
- t = {},
- key;
- opts = opts || {};
- for (key in T) {
- if (T.hasOwnProperty(key)) {
- t[key] = T[key];
- }
- }
- t.queue = [];
- t.sorter = opts.sorter || T.default_sorter;
- return t;
- },
- default_sorter: function (a, b) {
- return a.cost - b.cost;
- },
-
- push: function (value, cost) {
- var item = {value: value, cost: cost};
- this.queue.push(item);
- this.queue.sort(this.sorter);
- },
-
- pop: function () {
- return this.queue.shift();
- },
- empty: function () {
- return this.queue.length === 0;
- }
- }
- };
- if (typeof module !== 'undefined') {
- module.exports = dijkstra;
- }
|