class Dijkstra

# File lib/dijkstra.rb, line 4
def initialize(graph, source_vertex)
  @graph = graph
  @vertices = @graph.vertices
  @source_vertex = source_vertex
  @path_to = {}
  @distance_to = {}
  @pq = PriorityQueue.new
  compute_shortest_path
end

# File lib/dijkstra.rb, line 14
def shortest_path_to(vertex)
  return [] unless reachable?(vertex)
  return [] if @distance_to[vertex] == 0
  path = []
  while vertex != @source_vertex
    path.unshift(vertex)
    vertex = @path_to[vertex]
  end
  path.unshift(@source_vertex)
end

# File lib/dijkstra.rb, line 31
def compute_shortest_path
  update_distance_of_all_edges_to(Float::INFINITY)
  @distance_to[@source_vertex] = 0

  @pq.insert(@source_vertex, 0)
  while @pq.any?
    vertex = @pq.remove_min
    @vertices[vertex].edges.each do |edge|
      update(edge)
    end
  end
end

# File lib/dijkstra.rb, line 27
def reachable?(vertex)
  not @distance_to[vertex] == Float::INFINITY
end

# File lib/dijkstra.rb, line 50
def update(edge)
  raise "#{edge.to} doesn't exist, check edge[:to] in #{edge.inspect}" if @distance_to[edge.to].nil?
  return if @distance_to[edge.to] <= @distance_to[edge.from] + edge.weight
  @distance_to[edge.to] = @distance_to[edge.from] + edge.weight
  @path_to[edge.to] = edge.from
  @pq.insert(edge.to, @distance_to[edge.to])
end

# File lib/dijkstra.rb, line 44
def update_distance_of_all_edges_to(distance)
  @vertices.each do |key, value|
    @distance_to[key] = distance
  end
end