-
-
Save RLGGHC/602034e12a217dff7c0e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Challenge solution. Doesn't handle multiple shortest paths (just picks first | |
# one found, i.e. a node has a single predecessor on the shortest path, only | |
# overwritten when a shorter path is found). | |
# | |
# Assumes connections are bidirectional. Probably better to assume connections | |
# are directional, and double them up if they happen to be bidirectional. | |
# | |
# Problem statement consists of a graph with a start node and and end node. | |
# Node names are abitrary, so Start_node and End_node must be specified | |
Connections = [ | |
[ :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] | |
] | |
Start_node = :A | |
End_node = :G | |
#Node class tracks a nodes name, shortest distance calcualted so far from Start_node, and | |
#the node's predecessor on that shortest path | |
class Node | |
attr_accessor :name, :distance, :predecessor | |
def initialize(name) | |
@name = name | |
end | |
end | |
class Graph | |
def initialize(connections) | |
@connections = connections | |
end | |
def shortest_path(from, to) | |
#Create a new node if we haven't seen that name before | |
nodes=Hash.new {|h, k| h[k] = Node.new(k)} | |
#queue consists of nodes to analyse. New nodes will be queued only if not previously on the queue | |
queue = [Start_node] | |
#queued is those nodes previously analysed | |
queued = [] | |
nodes[from].distance = 0 | |
while(!queue.empty?) | |
working_node = queue.shift | |
connections_from(working_node).each do |connection| | |
#Connections are bi-directional and may be specified either way around | |
if connection[0] == working_node | |
target = connection[1] | |
else | |
target = connection[0] | |
end | |
#shortest path length to target is shortest path length to here, plus final connection | |
#if that's shorter than anything discovered so far, store new shortest path and predecessor | |
path_distance = nodes[working_node].distance + connection[2] | |
if (nodes[target].distance.nil? || path_distance < nodes[target].distance) | |
nodes[target].distance = path_distance | |
nodes[target].predecessor = working_node | |
end | |
#queue any new neighbor nodes we haven't seen before | |
unless queued.include?(target) | |
queue.push(target) | |
queued.push(target) | |
end | |
end | |
end | |
# Nodes now labelled with minimal distance | |
# i.e. shortest path has been calculated if it exists | |
# if end node not discovered by now, there is no route from start to end | |
return nil unless nodes.has_key?(to) | |
# Backtrack from end node until we reach the start node | |
# (which we will do, as the end node was discovered) | |
shortest = [] | |
working_node=to | |
until working_node == from | |
predecessor = nodes[nodes[working_node].predecessor] | |
# Again, connections are bidirectional and may be specified in either order. | |
shortest << @connections.select do |connection| | |
(connection[0] == working_node && connection[1] == predecessor.name) || | |
(connection[1] == working_node && connection[0] == predecessor.name) | |
end[0] | |
working_node = predecessor.name | |
end | |
shortest | |
end | |
def connections_from(node_name) | |
@connections.select{|r| r[0] == node_name || r[1] == node_name} | |
end | |
def redundant_connections(from, to) | |
#Assumes all paths are redundant if shortest path does not exist | |
if (shortest = shortest_path(from, to)).nil? | |
return @connections | |
else | |
return @connections - shortest | |
end | |
end | |
end | |
g = Graph.new(Connections) | |
p g.redundant_connections(Start_node, End_node) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment