I (thought) I had a need for a shortest path implementation across a graph. Turns out I don’t, but here it is in case it is useful to someone else.

It is adapted from a javascript implementation.

To use: new Dijkstra().find_path(source_node, dest_node)

source_node and dest_node should have methods called “adjacent_nodes” that knows about the nodes that they are attached to.

This implementation assumes equal weighting on all links.

class Dijkstra constructor: () -> @predecessors = {} single_source_shortest_paths: (s, d) -> costs = {} costs[s] = 0 open = {'0': [s]} keys = (obj) -> keys = [] for key of obj keys.push(key) keys.sort(sorter) keys sorter = (a, b) -> parseFloat(a) - parseFloat(b); add_to_open = (cost, v) -> key = '' + cost; open[key] ?= []; open[key].push(v); while (open) # In the nodes remaining in graph, # find the node, u, that currently has the shortest path from s. key = keys(open).pop() break if ! key? bucket = open[key] u = bucket.shift() delete open[key] if (bucket.length == 0) # Current cost of path from s to u. w_of_s_to_u = parseFloat(key) # v is the node across the current edge from u. for v in u.adjacent_nodes() w_of_s_to_v = w_of_s_to_u + 1 costs[v] ?= Infinity if costs[v] > w_of_s_to_v costs[v] = w_of_s_to_v add_to_open(w_of_s_to_v, v) @predecessors[v] = u # If a destination node was specified and we reached it, we're done. if v.hash == d.hash open = null break costs[d] ? Infinity extract_shortest_path_from_predecessor_list: (d) -> nodes = []; u = d while (u) nodes.push(u) u = @predecessors[u] nodes.reverse() find_cost: (s, d) -> @single_source_shortest_paths(s, d) find_path: (s, d) -> cost = @single_source_shortest_paths(s, d) if cost < Infinity return @extract_shortest_path_from_predecessor_list(d) throw new Error("Could not find a path from #{s} to #{d}.")