An implementation of Dijkstra's algorithm in Ruby

dijkstra.rb

# A pure Ruby implementation of https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
#
# Takes a graph in hash form, e.g. { 'A' => ['B', 'C'], 'B' => ['D'], 'C' => ['D'] },
# and a source node, e.g. 'A', and returns the distances to every reachable node and a hash of "next hops" for each node.
def dijkstra(graph, source)
  q = graph.keys
  prev = {}

  dist = Hash.new(Float::INFINITY)
  dist[source] = 0

  until q.empty?
    u = q.min_by { |u| dist[u] }

    q.delete(u)

    graph[u].each do |v|
      alt = dist[u] + 1

      if alt < dist[v]
        dist[v] = alt
        prev[v] = u
      end
    end
  end

  [dist, prev]
end