From: Dominik Bathon <dbatml@...>
Date: 2005-05-13T06:10:21+09:00
Subject: Re: [SUMMARY] Amazing Mazes (#31)

Nice summary, thanks.

One other point I found out today:
We don't really need Dijkstra's algorithm for the mazes, because all edges  
have weight 1. In this case a simple breadth-first search is sufficient.  
So build_prev_hash can be simplified to the following:

       def build_prev_hash(start, stop_at=nil)
             prev={start=>[nil, 0]} # hash to be returned
             # positions which we have seen, but we are not yet sure about
             # the shortest path to them (the value is length of the path,
             # for delete_min_value):
             active=[start]
             until active.empty?
                   # get the position with the shortest path from the
                   # active list
                   cur=active.shift
                   return prev if cur==stop_at
                   newlength=prev[cur][1]+1 # path to cur length + 1
                   neighbors(cur).each { |n|
                         # ignore unreachable
                         next if wall_between?(cur, n)
                         # was n already visited
                         next if prev[n]
                         # add new position to active list
                         active << n
                         # set prev and length
                         prev[n]=[cur, newlength]
                   }
             end
             prev
       end

The active list is now an Array instead of a Hash and we just use it as  
fifo, because the positions/paths that were found first are the shortest.  
So there is also no more need for Hash#delete_min_value. And it gets even  
faster ;-)

Dominik