Dijkstra's algorithm implemented in ruby

graph.rb

#ruby 2.3.1 recomended
class Graph
  attr_reader :graph, :nodes, :previous, :distance #getter methods
  INFINITY = 1 << 64

  def initialize
    @graph = {} # the graph // {node => { edge1 => weight, edge2 => weight}, node2 => ...
    @nodes = Array.new
  end

# connect each node with target and weight
  def connect_graph(source, target, weight)
    if (!graph.has_key?(source))
      graph[source] = {target => weight}
    else
      graph[source][target] = weight
    end
    if (!nodes.include?(source))
      nodes << source
    end
  end

# connect each node bidirectional
  def add_edge(source, target, weight)
    connect_graph(source, target, weight) #directional graph
    connect_graph(target, source, weight) #non directed graph (inserts the other edge too)
  end


# based of wikipedia's pseudocode: http://en.wikipedia.org/wiki/Dijkstra's_algorithm


  def dijkstra(source)
    @distance={}
    @previous={}
    nodes.each do |node|#initialization
      @distance[node] = INFINITY #Unknown distance from source to vertex
      @previous[node] = -1 #Previous node in optimal path from source
    end

    @distance[source] = 0 #Distance from source to source

    unvisited_node = nodes.compact #All nodes initially in Q (unvisited nodes)

    while (unvisited_node.size > 0)
      u = nil;

      unvisited_node.each do |min|
        if (not u) or (@distance[min] and @distance[min] < @distance[u])
          u = min
        end
      end

      if (@distance[u] == INFINITY)
        break
      end

      unvisited_node = unvisited_node - [u]

      graph[u].keys.each do |vertex|
        alt = @distance[u] + graph[u][vertex]

        if (alt < @distance[vertex])
          @distance[vertex] = alt
          @previous[vertex] = u  #A shorter path to v has been found
        end

      end

    end

  end


# To find the full shortest route to a node

  def find_path(dest)
    if @previous[dest] != -1
      find_path @previous[dest]
    end
    @path << dest
  end


# Gets all shortests paths using dijkstra

  def shortest_paths(source)
    @graph_paths=[]
    @source = source
    dijkstra source
    nodes.each do |dest|
      @path=[]

      find_path dest

      actual_distance=if @distance[dest] != INFINITY
                        @distance[dest]
                      else
                        "no path"
                      end
      @graph_paths<< "Target(#{dest})  #{@path.join("-->")} : #{actual_distance}"
    end
    @graph_paths
  end

  # print result

  def print_result
    @graph_paths.each do |graph|
      puts graph
    end
  end

end

if __FILE__ == $0
#sample input as per http://en.wikipedia.org/wiki/Dijkstra's_algorithm
  gr = Graph.new
  gr.add_edge("a", "c", 7)
  gr.add_edge("a", "e", 14)
  gr.add_edge("a", "f", 9)
  gr.add_edge("c", "d", 15)
  gr.add_edge("c", "f", 10)
  gr.add_edge("d", "f", 11)
  gr.add_edge("d", "b", 6)
  gr.add_edge("f", "e", 2)
  gr.add_edge("e", "b", 9)
  gr.shortest_paths("a")
  gr.print_result 

end

graph_spec.rb

#rspec based testing 
#rspec 3.4.0 recomended
#to run tests 'rspec spec graph_spec.rb --format=documentation'

require 'graph' #require ruby file where the algorithm written
describe Graph do
  let(:new_graph) {
    Graph.new
  }
  context "graph creation" do
    it 'should initialize empty graph' do
      graph=new_graph
      expect(graph.graph).to eq({})
    end

    it 'should initialize empty nodes' do
      graph=new_graph
      expect(graph.nodes).to eq([])
    end

    it 'is connect graph with source,target,weight #connect_graph' do
      graph=new_graph
      graph.connect_graph("a", "b", 5)
      expect(graph.graph).to eq({"a" => {"b" => 5}})
    end

    it 'is connect node with source,target,weight #connect_graph' do
      graph=new_graph
      graph.connect_graph("a", "b", 5)
      expect(graph.nodes).to include("a")
    end

    it 'is graph connect  bidirectional #add_edge' do
      graph=new_graph
      graph.add_edge("a", "b", 5)
      expect(graph.graph.keys).to eq(["a", "b"])
    end
  end

  context "Dijkstra's_algorithm" do
    it 'is dijkstras algorithm works to track distance #dijkstra' do
      graph=new_graph
      graph.add_edge("a", "b", 5)
      graph.add_edge("b", "c", 3)
      graph.add_edge("c", "d", 1)
      graph.dijkstra("a")
      expect(graph.distance).to eq({"a"=>0, "b"=>5, "c"=>8, "d"=>9})
    end

    it 'is dijkstras algorithm works to track connected node #dijkstra' do
      graph=new_graph
      graph.add_edge("a", "b", 5)
      graph.add_edge("b", "c", 3)
      graph.add_edge("c", "d", 1)
      graph.dijkstra("a")
      expect(graph.previous).to eq({"a"=>-1, "b"=>"a", "c"=>"b", "d"=>"c"})
    end

    it 'is dijkstra algorithm find shortest path #shortest_paths' do
      graph=new_graph
      graph.add_edge("a", "b", 5)
      graph.add_edge("b", "c", 3)
      graph.add_edge("c", "d", 1)
      expect(graph.shortest_paths("a")).to include ("Target(c)  a-->b-->c : 8")
    end


  end


end

Made it considerably faster, especially for large sparse graphs, here: https://gist.github.com/piki/dc6a3ee8eb90be0f5c61dd972988094f

The trick is to manage a queue of unvisited nodes, rather than pushing all of them into unvisited_node at once. That's adapted from the (array, not priority queue) variation here: https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Using_a_priority_queue.