Recently in a LinkedIn LED hack day, I got a chance to play around with data to analyze the social graph. In order to compute some results in real-time, I needed an efficient way to find the shortest path between two nodes in a graph and Dijkstra’s algorithm came to mind.

Dijkstra’s algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing. –Wikipedia

I searched on the web a bit, but I couldn’t find a Ruby implementation so I decided to write my own. It ended up being pretty easy to implement. I decided to post it here in case someone in the future wants to save 30 minutes or so implementing it. Please note that it makes use of priority queue library which is written by K. Kodama.

require 'pqueue'

class Algorithm
INFINITY = 1 << 32

def self.dijkstra(source, edges, weights, n)
visited = Array.new(n, false)
shortest_distances = Array.new(n, INFINITY)
previous = Array.new(n, nil)
pq = PQueue.new(proc {|x,y| shortest_distances[x] < shortest_distances[y]})

pq.push(source)
visited = true
shortest_distances = 0

while pq.size != 0
v = pq.pop
visited[v] = true
if edges[v]
edges[v].each do |w|
if !visited[w] and shortest_distances[w] > shortest_distances[v] + weights[v][w]
shortest_distances[w] = shortest_distances[v] + weights[v][w]
previous[w] = v
pq.push(w)
end
end
end
end
return [shortest_distances, previous]
end
end

Please let me know if you have any questions.