RPCFN: Short Circuit (#3)やってみた

チャレンジしました
AからGまでの最短経路を探した上で、不要な経路を出力するというものです
RPCFN: Short Circuit (#3)
ダイクストラ法を参考にしました。正面衝突ブチ当たり
ダイクストラ法（最短経路問題）

コード

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

実行結果

# ruby short_circuit.rb 
[{:from=>"A", :to=>"B", :len=>50},
 {:from=>"B", :to=>"C", :len=>250},
 {:from=>"B", :to=>"E", :len=>250},
 {:from=>"C", :to=>"E", :len=>350},
 {:from=>"D", :to=>"F", :len=>400},
 {:from=>"E", :to=>"G", :len=>200}]