redredred

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