## Dijkstra’s shortest path algorithm in Coffeescript

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}.")```

This entry was posted on November 21st, 2010.