ruby on rails - How do I make a path out of a hash? -

i trying locate route of shortest path of map(connected nodes weight/distance).

let's assume have hash this:

{"a"=>{"b"=>1, "e"=>1}, "b"=>{"a"=>1, "c"=>1, "f"=>1}, "c"=>{"b"=>1, "d"=>1, "g"=>1}, "d"=>{"c"=>1, "h"=>1}, "e"=>{"f"=>1, "a"=>1, "i"=>1}, "f"=>{"e"=>1, "g"=>1, "b"=>1, "j"=>1}, "g"=>{"f"=>1, "h"=>1, "c"=>1, "k"=>1}, "h"=>{"g"=>1, "d"=>1, "l"=>1}, "i"=>{"j"=>1, "e"=>1, "m"=>1}, "j"=>{"i"=>1, "k"=>1, "f"=>1, "n"=>1}, "k"=>{"j"=>1, "l"=>1, "g"=>1, "o"=>1}, "l"=>{"k"=>1, "h"=>1, "p"=>1}, "m"=>{"n"=>1, "i"=>1}, "n"=>{"m"=>1, "o"=>1, "j"=>1}, "o"=>{"n"=>1, "p"=>1, "k"=>1}, "p"=>{"o"=>1, "l"=>1}}  

now want traverse , make path hash. example:

from source destination: l

output should be: either a -> e -> -> j -> k -> l or a -> b -> c -> d -> h -> l.

here function wrote:

def find_path(src, dst, init = [])   path = [src]   neighbors = self.neighbors(src)   puts "src: #{src}"   puts "dst: #{dst}"   # puts "node: #{node}"   puts "init: #{init}"   puts "path: #{path}"   puts "----\n"    if neighbors.include?(dst)     path.push(dst)   else     path.push(@nodes[src].keys.map{|k| k unless init.flatten.include? k }.reject(&:blank?).each{|key| self.find_path(key, dst, init << path) } )   end   return path end 

but, prints : ["a", ["b", "e"]]

which not desired output, can tell me how go make work? thanks.

update: used locating route of shortest path of map(connected nodes weight/distance). here details on trying achieve in question: https://gist.github.com/suryart/6439102

the original hash:

h = {"a"=>{"b"=>1, "e"=>1}, "b"=>{"a"=>1, "c"=>1, "f"=>1}, "c"=>{"b"=>1, "d"=>1, "g"=>1}, "d"=>{"c"=>1, "h"=>1}, "e"=>{"f"=>1, "a"=>1, "i"=>1}, "f"=>{"e"=>1, "g"=>1, "b"=>1, "j"=>1}, "g"=>{"f"=>1, "h"=>1, "c"=>1, "k"=>1}, "h"=>{"g"=>1, "d"=>1, "l"=>1}, "i"=>{"j"=>1, "e"=>1, "m"=>1}, "j"=>{"i"=>1, "k"=>1, "f"=>1, "n"=>1}, "k"=>{"j"=>1, "l"=>1, "g"=>1, "o"=>1}, "l"=>{"k"=>1, "h"=>1, "p"=>1}, "m"=>{"n"=>1, "i"=>1}, "n"=>{"m"=>1, "o"=>1, "j"=>1}, "o"=>{"n"=>1, "p"=>1, "k"=>1}, "p"=>{"o"=>1, "l"=>1}}  

converting original hash since format sucks:

h.keys.each{|k| h[k] = h[k].keys} h.default = [] 

the method:

def find_path h, src, dst   paths = [[src]]   loop     paths = paths.flat_map |path|       h[path.last].map |nekst|         = [*path, nekst]         a.last == dst ? (return a) :       end     end   end end 

trying it:

find_path(h, "a", "l") # => ["a", "b", "c", "d", "h", "l"] 

notice if there no solution, loop may run forever. might want limit adding limit length.