# Implementing Dijkstra’s Algorithm in Ruby

##
September 19, 2008

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[source] = true shortest_distances[source] = 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.