# Optimizing breadth-first-search code

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 if (!direct_connection?(current_element, next_element)) return false end path.shift end return true end  • 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. – David Parker Oct 7 '14 at 19:28 ## 1 Answer 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"]