Dijkstra's algorithm implemented in ruby

graph.rb

#ruby 2.3.1 recomended
require 'set'

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 = Set.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
    nodes << source
  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

    queue = Set.new
    queue << source

    while !queue.empty?
      u = queue.min_by{|n| @distance[n]}

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

      queue.delete(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
          queue << vertex
        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 ||= []
    @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(Set.new)
    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