secret
Last active

  • 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 54 55 56
routes =
[
{ :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},
]
 
def search_min_path(available_routes, done_node, min_len=0, min_path=[])
available_routes -= min_path
 
done_undone_path = available_routes.select{|e| e[:from] == done_node}.min{|a,b| a[:len] <=> b[:len]}
return min_path.pop unless done_undone_path
undone_node = done_undone_path[:to]
 
if undone_node == "G"
return done_undone_path
end
 
undone_undone_next_path = available_routes.select{|e| e[:from] == undone_node}.min{|a,b| a[:len] <=> b[:len]}
undone_undone_next_node = undone_undone_next_path[:to]
done_undone_next_path = available_routes.detect{|e| e[:from] == done_node && e[:to] == undone_undone_next_node}
 
if done_undone_next_path && done_undone_next_path[:len] <= done_undone_path[:len] + undone_undone_next_path[:len]
min_len = done_undone_next_path[:len]
return undone_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]
min_path.push done_undone_path
else
min_path.unshift done_undone_path
end
min_path = search_min_path(available_routes, done_node, min_len, min_path)
end
 
min_path
end
 
done_node = "A"
stack = []
 
while(done_node != "G")
path = search_min_path(routes, done_node)
done_node = path[:to]
stack << path
end
 
require 'pp'
pp routes - stack

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.