Dijkstra 5 lines

class Edge
  attr_accessor :src, :dest, :length

  def initialize(src, dest, length = 1)
    @src = src
    @dest = dest
    @length = length
  end
end

class Graph < Array
  attr_reader :edges

  def initialize
    @edges = []
  end

  def connect(src, dest, length = 1)
    @edges.push Edge.new(src, dest, length)
  end

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

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

end

class Dijkstra

  def initialize(graph, src, dest)
    @graph = graph
    @src = src
    @dest = dest
    reset
  end

  def reset
    @dist = {}
    @prev = {}
    @graph.each { |vertex| @dist[vertex] = @prev[vertex] = nil }
    @dist[@src] = 0
    @vertices = @graph.clone
  end

  def find_nearest_vertex
    @nearest_vertex = @vertices.inject do |a, b|
      next b unless @dist[a]
      next a if !@dist[b] || @dist[a] < @dist[b]
      b
    end
  end

  def update_weights(vertex)
    alt = @dist[@nearest_vertex] + @vertices.length_between(@nearest_vertex, vertex)
    if @dist[vertex].nil? or alt < @dist[vertex]
      @dist[vertex] = alt
      @prev[@vertices] = @nearest_vertex
    end
  end

  def run_through_neighbours
    @vertices.neighbors(@nearest_vertex).each do |vertex|
      update_weights(vertex)
    end
    @vertices.delete @nearest_vertex
  end

  def run
    until @vertices.empty?
      return @dist[@dest] if @dest and find_nearest_vertex == @dest
      run_through_neighbours
    end
    @dest ? nil : @dist
  end

end

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

p Dijkstra.new(graph, 1, 4).run