shortest_path.rb

def shortest_path(v,w)
  raise ArgumentError unless path?(v,w) to_edge = []
  bfs(w) { |v1,v2| to_edge[v2] = v1 } result = []
  x= v
  while x != w
    result << x
    x = to_edge[x]
  end
  result << x
end

def path?(v1,v2)
  return false if v1 < 0 or vertices <= v1
  return false if v2 < 0 or vertices <= v2
  dfs(v1) do |v,w|
    return true if w == v2
  end
  false 
end