Optimizing breadth-first-search code

Question

I wrote code using some kind of breadth-first-search algorithm in order to find a path (any path!) from a start point to an end point. There are no weights/different distances involved from path-to path-so I am not sure I should use Dijkstra's algorithm.

However, I am required to find a solution that can search for and return a path within a second (while this current code can complete it in five seconds). Assuming my code is inefficient, what can I do better?

$visited = Array.new
$queue = Array.new
def find_path (start, endpoint)
 returnArray = Array.new
 start = start.to_s
 endpoint = endpoint.to_s
 $queue.push(start)
 nextPaths = get_next_paths(start)
 if start == endpoint
 return returnArray.push(endpoint)
 else
 $visited.push(start)
 $queue.pop(start.to_i)
 nextPaths.each { |i| next if $visited.include?(i); 
 $queue.push(i)
 returnArray = find_path(i.to_i, endpoint.to_i)
 if returnArray == nil
 next
 elsif !returnArray.empty?
 returnArray.unshift(start)
 return returnArray
 end
 }
 end
 if !$queue.empty?
 return []
 else
 return nil
 end
end
def get_next_paths(id)
 return $h[id.to_s]
end
def direct_connection?(id1, id2)
 next_paths = get_next_paths(id1) 
 return (next_paths!=nil and next_paths.include?(id2.to_s))
end
def valid_path?(path)
 while (path.length>1)
 current_element = path.first
 next_element = path[1]
 if (!direct_connection?(current_element, next_element))
 return false
 end
 path.shift
 end
 return true
end

• David Parker: Using Djkstra will give you the shortest path, and may also be more efficient if it can return the path and stop searching for paths right after. There is a modified version of Djkstra which is much faster in most cases, it is called A* <en.wikipedia.org/wiki/A*_search_algorithm>. A* Is very popular in the video game industry for its high general case performance.

Answer 1

I'm not sure if I understand your input data correctly, since I don't get this $queue.pop(start.to_i), but:

1. I won't mention codestyle issues -- I'll talk about algorithm.

2. Looks like your search is really Depth-first, since it doesn't find the shortest path:

   $h = {?0=>[?1,?2,?3], ?1=>[?3], ?3=>[?4]}
   p find_path ?0,?4
   => ["0", "1", "3", "4"]
   

   it is because:

   • it calls recursion immediately before iterating the rest of child nodes
   • in real Breadth-first you have to store a lot of paths at the same time
3. Use Set instead of Array for visited, since it looks up immediately instead of searching the value from the beginning of the list.
4. The easiest way to implement both of these searches with no risk of stack overflow is to use stack of the next states, that we should analyze instead of recursion. Also in this way we don't need global variables or other namespace tricks, since we just do the loop, where path is used instead of $queue and returnArray:

Take this code:

def find_path start, endpoint
 require "set"
 visited = Set.new
 stack = [[start.to_s]]
 until stack.empty?
 path = stack.shift
 start = path.last
 get_next_paths(start).each do |i|
 return path.push i if i == endpoint.to_s
 next if visited.include? i
 visited << start
 stack.push path+[i]
 end
 end
end

And run this:

$h = {?0=>[?3,?2,?1], ?1=>[?5], ?3=>[?4], ?5=>[?4], ?2=>[], ?4=>[]}
p find_path_ ?0,?4

The fun thing is how it is now easy to switch between Depth and Breadth by just replacing .shift with .pop:

["0", "3", "4"]
["0", "1", "5", "4"]