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

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"]