Adam Lum's solution for RPCFN #3 (Short Circuit)

short_circuit.rb

# Adam Lum's solution for RPCFN #3
# http://rubylearning.com/blog/2009/10/30/rpcfn-short-circuit-3/

INFINITY = 1 << 64

def dijkstra (graph, start, destination)
  # Initialize
  nodes = []
  graph.each do |c|
    nodes << c[0]
    nodes << c[1]
  end
  nodes.sort!.uniq!
  node_list = {}
  (0..nodes.size - 1).each do |i|
    node_list[nodes[i]] = {"dist" => INFINITY, "prev" => ""}
  end
  node_list[start]["dist"] = 0
  # Dijkstra's Algorithm
  while (nodes.size > 0)
    u = nil
    node_list.each do |min|
      if (nodes.include?(min[0]))
        if ((not u) || (min[1]["dist"] && min[1]["dist"] <= u[1]["dist"]))
    	    u = min
    	  end
  	  end
    end
    if (u[1]["dist"] == INFINITY)
      return {}
    end
    nodes.delete(u[0])
    graph.each do |c|
      alt = -1
      node_key = ""
      prev_node_key = ""
      if (c[0] == u[0])
        if (nodes.include?(c[1]))
          node_key = c[1]
          prev_node_key = c[0]
          alt = u[1]["dist"] + c[2]
        end
      elsif (c[1] == u[0])
        if (nodes.include?(c[0]))
          node_key = c[0]
          prev_node_key = c[1]
          alt = u[1]["dist"] + c[2]
        end
      end
      if ((alt != -1) && (alt < node_list[node_key]["dist"]))
        node_list[node_key]["dist"] = alt
        node_list[node_key]["prev"] = prev_node_key 
      end
    end
  end
  node_list
end

def shortest_path(graph, start, destination)
  path_array = []
  node_list = dijkstra(graph, start, destination)
  target = destination
  while (node_list[target]["prev"] != "")
    path_array << [node_list[target]["prev"], target]
    target = node_list[target]["prev"]
  end
  path_array.reverse!
end

def redundant_elements(graph, start, destination)
  shortest = shortest_path(graph, start, destination)
  shortest.each do |s|
    graph.delete_if {|g| (g.include?(s[0]) && g.include?(s[1]))}
  end
  graph
end

# The graph provided from the RPCFN #3
circuit = [
   ["A", "B", 50],
   ["A", "D", 150],
   ["B", "C", 250],
   ["B", "E", 250],
   ["C", "E", 350],
   ["C", "D", 50],
   ["C", "F", 100],
   ["D", "F", 400],
   ["E", "G", 200],
   ["F", "G", 100],
]