3 /******************************************************************************
6 * Dijkstra path-finding functions. Adapted from the Dijkstar Python project.
9 * Wyatt Baldwin <self@wyattbaldwin.com>
12 * Licensed under the MIT license.
14 * http://www.opensource.org/licenses/mit-license.php
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 *****************************************************************************/
25 single_source_shortest_paths: function(graph, s, d) {
26 // Predecessor map for each node that has been encountered.
27 // node ID => predecessor node ID
28 var predecessors = {};
30 // Costs of shortest paths from s to all nodes encountered.
35 // Costs of shortest paths from s to all nodes encountered; differs from
36 // `costs` in that it provides easy access to the node that currently has
37 // the known shortest path from s.
38 // XXX: Do we actually need both `costs` and `open`?
39 var open = dijkstra.PriorityQueue.make();
47 cost_of_s_to_u_plus_cost_of_e,
50 while (!open.empty()) {
51 // In the nodes remaining in graph that have a known cost from s,
52 // find the node, u, that currently has the shortest path from s.
55 cost_of_s_to_u = closest.cost;
57 // Get nodes adjacent to u...
58 adjacent_nodes = graph[u] || {};
60 // ...and explore the edges that connect u to those nodes, updating
61 // the cost of the shortest paths to any or all of those nodes as
62 // necessary. v is the node across the current edge from u.
63 for (v in adjacent_nodes) {
64 if (adjacent_nodes.hasOwnProperty(v)) {
65 // Get the cost of the edge running from u to v.
66 cost_of_e = adjacent_nodes[v];
68 // Cost of s to u plus the cost of u to v across e--this is *a*
69 // cost from s to v that may or may not be less than the current
71 cost_of_s_to_u_plus_cost_of_e = cost_of_s_to_u + cost_of_e;
73 // If we haven't visited v yet OR if the current known cost from s to
74 // v is greater than the new cost we just found (cost of s to u plus
75 // cost of u to v across e), update v's cost in the cost list and
76 // update v's predecessor in the predecessor list (it's now u).
77 cost_of_s_to_v = costs[v];
78 first_visit = (typeof costs[v] === 'undefined');
79 if (first_visit || cost_of_s_to_v > cost_of_s_to_u_plus_cost_of_e) {
80 costs[v] = cost_of_s_to_u_plus_cost_of_e;
81 open.push(v, cost_of_s_to_u_plus_cost_of_e);
88 if (typeof d !== 'undefined' && typeof costs[d] === 'undefined') {
89 var msg = ['Could not find a path from ', s, ' to ', d, '.'].join('');
96 extract_shortest_path_from_predecessor_list: function(predecessors, d) {
102 predecessor = predecessors[u];
109 find_path: function(graph, s, d) {
110 var predecessors = dijkstra.single_source_shortest_paths(graph, s, d);
111 return dijkstra.extract_shortest_path_from_predecessor_list(
116 * A very naive priority queue implementation.
119 make: function (opts) {
120 var T = dijkstra.PriorityQueue,
125 if (T.hasOwnProperty(key)) {
130 t.sorter = opts.sorter || T.default_sorter;
134 default_sorter: function (a, b) {
135 return a.cost - b.cost;
139 * Add a new item to the queue and ensure the highest priority element
140 * is at the front of the queue.
142 push: function (value, cost) {
143 var item = {value: value, cost: cost};
144 this.queue.push(item);
145 this.queue.sort(this.sorter);
149 * Return the highest priority element in the queue.
152 return this.queue.shift();
156 return this.queue.length === 0;
162 // node.js module exports
163 if (typeof module !== 'undefined') {
164 module.exports = dijkstra;