Skip to content

Instantly share code, notes, and snippets.

@adamlum
Created January 22, 2010 23:55
Show Gist options
  • Save adamlum/284303 to your computer and use it in GitHub Desktop.
Save adamlum/284303 to your computer and use it in GitHub Desktop.
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