Dijkstra Shortest Path Algorithm in Ruby

dijkstra.rb

#!/usr/bin/ruby1.9.1 -Kw
# -*- coding: utf-8 -*-

class Edge
  attr_accessor :src, :dst, :length
  
  def initialize(src, dst, length = 1)
    @src = src
    @dst = dst
    @length = length
  end
end

class Graph < Array
  attr_reader :edges
  
  def initialize
    @edges = []
  end
  
  def connect(src, dst, length = 1)
    unless self.include?(src)
      raise ArgumentException, "No such vertex: #{src}"
    end
    unless self.include?(dst)
      raise ArgumentException, "No such vertex: #{dst}"
    end
    @edges.push Edge.new(src, dst, length)
  end
  
  def connect_mutually(vertex1, vertex2, length = 1)
    self.connect vertex1, vertex2, length
    self.connect vertex2, vertex1, length
  end

  def neighbors(vertex)
    neighbors = []
    @edges.each do |edge|
      neighbors.push edge.dst if edge.src == vertex
    end
    return neighbors.uniq
  end

  def length_between(src, dst)
    @edges.each do |edge|
      return edge.length if edge.src == src and edge.dst == dst
    end
    nil
  end

  def dijkstra(src, dst = nil)
    distances = {}
    previouses = {}
    self.each do |vertex|
      distances[vertex] = nil # Infinity
      previouses[vertex] = nil
    end
    distances[src] = 0
    vertices = self.clone
    until vertices.empty?
      nearest_vertex = vertices.inject do |a, b|
        next b unless distances[a]
        next a unless distances[b]
        next a if distances[a] < distances[b]
        b
      end
      break unless distances[nearest_vertex] # Infinity
      if dst and nearest_vertex == dst
        return distances[dst]
      end
      neighbors = vertices.neighbors(nearest_vertex)
      neighbors.each do |vertex|
        alt = distances[nearest_vertex] + vertices.length_between(nearest_vertex, vertex)
        if distances[vertex].nil? or alt < distances[vertex]
          distances[vertex] = alt
          previouses[vertices] = nearest_vertex
          # decrease-key v in Q # ???
        end
      end
      vertices.delete nearest_vertex
    end
    if dst
      return nil
    else
      return distances
    end
  end
end

graph = Graph.new
(1..6).each {|node| graph.push node }
graph.connect_mutually 1, 2, 7
graph.connect_mutually 1, 3, 9
graph.connect_mutually 1, 6, 14
graph.connect_mutually 2, 3, 10
graph.connect_mutually 2, 4, 15
graph.connect_mutually 3, 4, 11
graph.connect_mutually 3, 6, 2
graph.connect_mutually 4, 5, 6
graph.connect_mutually 5, 6, 9

p graph
p graph.length_between(2, 1)
p graph.neighbors(1)
p graph.dijkstra(1, 5)

Line 76 should be

previouses[vertex] = nearest_vertex

Also, Float::INFINITY can be used instead of nil, if float is used in length instead of integer.

I've added the calculated paths to the dijkstra method's return value in a fork if anyone else needs that functionality:

https://gist.github.com/roganartu/9407316

I'm learning Ruby as a first language and still relatively new to programming so I could be very wrong but, the "previous" hash as currently implemented doesn't seem to be doing anything. My reasoning is as follows:

On line 53 the "previous" hash is created.
On line 56 the hash is populated with each node in the graph and it's value is set to nil.
On line 76 the value is changed to the "nearest_vertex".
Otherwise the "previous" hash is not mentioned anywhere else in the program. So unless I'm wrong the hash is never used for anything.
Finally, I ran the program using several small data sets and in spite of this oversight the program seems to produce the correct answer.

Am I missing something? Is the program flawed in some way without "previous" correctly implemented?
Thank you.

Hello msimcoe,

I saw your comment and noticed the same thing.

It seems traditionally this is part of Dijkstra's Algorithm, and CAN be used if you need to get the shortest path to a particular destination. This is because the value is the previous vertex visited along it's path from the source.

So it could be included in the return statements, but since it's not actually returned it used it probably could be deleted.