secret
Created — forked from s5ot/sogoohta.rb

  • Download Gist
sogoohta.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.