Skip to content

@RLGGHC /sogoohta.rb secret forked from s5ot/sogoohta.rb

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
paths =
[
{:from => "A", :to => "B", :len => 50},
{:from => "A", :to => "D", :len => 150},
{:from => "B", :to => "C", :len => 250},
{:from => "B", :to => "E", :len => 250},
{:from => "C", :to => "E", :len => 350},
{:from => "D", :to => "C", :len => 50},
{:from => "C", :to => "F", :len => 100},
{:from => "D", :to => "F", :len => 400},
{:from => "E", :to => "G", :len => 200},
{:from => "F", :to => "G", :len => 100},
]
done_node = "A"
min_paths = []
def search_min_path(available_paths, done_node, min_len=0, searched_path=[])
available_paths -= searched_path
done_undone_path = available_paths.select{|path| path[:from] == done_node}.min{|a,b| a[:len] <=> b[:len]}
return searched_path.pop unless done_undone_path
undone_node = done_undone_path[:to]
return done_undone_path if undone_node == "G"
undone_undone_next_path = available_paths.select{|path| path[:from] == undone_node}.min{|a,b| a[:len] <=> b[:len]}
undone_next_node = undone_undone_next_path[:to]
done_undone_next_path = available_paths.detect{|path| path[:from] == done_node && path[:to] == undone_next_node}
if done_undone_next_path && done_undone_next_path[:len] <= done_undone_path[:len] + undone_undone_next_path[:len]
return done_undone_next_path
else
if done_undone_path[:len] + undone_undone_next_path[:len] < min_len || min_len == 0
min_len = done_undone_path[:len] + undone_undone_next_path[:len]
searched_path.push done_undone_path
else
searched_path.unshift done_undone_path
end
min_path = search_min_path(available_paths, done_node, min_len, searched_path)
end
min_path
end
while(done_node != "G")
path = search_min_path(paths, done_node)
done_node = path[:to]
min_paths.push path
end
require 'pp'
pp paths - min_paths
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.