Adam Lum's solution for RPCFN #3 (Short Circuit)
# 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], | |
] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment