Implementing Dijkstra's algorithm with Fibonacci Heap

dijkstra_with_fibonacci_heap.rb

require 'fibonacci_heap'

# Assuming `graph` is an object with the following interface that stores vertices as `FibonacciHeap::Node`
# instances and `source` is a `FibonacciHeap::Node`:
#
# * `graph.vertices`: return an Enumerable of all vertices in the graph
# * `graph.neighbours(u)`: return an Enumerable of all vertices that neighbour a given vertex `u`
# * `graph.length(u, v)`: return the numeric weight of the edge between two given vertices `u` and `v`
def dijkstra(graph, source)
  dist = Hash.new(Float::INFINITY)
  dist[source] = 0
  
  prev = {}
  
  q = FibonacciHeap::Heap.new
  
  graph.vertices.each do |v|
     q.insert(v, dist[v])
  end
  
  until q.empty?
    u = q.pop
    
    graph.neighbours(u).each do |v|
      alt = dist[u] + graph.length(u, v)
      next unless alt < dist[v]
      
      dist[v] = alt
      prev[v] = u
      q.decrease_key(v, alt)
    end
  end
  
  [dist, prev]
end