Skip to content

Instantly share code, notes, and snippets.

Last active July 15, 2018 16:14
What would you like to do?
Implementing Dijkstra's algorithm with Fibonacci Heap
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 =
dist[source] = 0
prev = {}
q =
graph.vertices.each do |v|
q.insert(v, dist[v])
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)
[dist, prev]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment