2

For simplicity sake, suppose I have the graph:

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

In which I want to use a breadth-first search to travel from A to P by the shortest path, where positions designated by | are restricted areas. How can I achieve this result? I've always seen the breadth-first search used to find some location (P in this case), but I haven't seen any implementation used to store path distances and compute the shortest one (nor efficient methods to store previously visited locations and exclude them from further scrutiny). Also, what queue is typically suggested for graphs that are necessarily large and require extensive pushes and pops?

Bob John
  • 3,688
  • 14
  • 43
  • 57
  • Might be relevant to look up the "A*" (has "weights") and Djikstra's algorithms .. –  Jan 30 '13 at 01:31
  • @pst Well, yes, but the problem sounds like one often poised to students just starting a graph algorithms unit. Bob may want to do this the conceptually simpler way first. – dmckee --- ex-moderator kitten Jan 30 '13 at 01:33
  • Thank you both. I'm working with BFS, so it's what I want to implement my algorithm in. I know of other search algorithms, but this is the one I will use. – Bob John Jan 30 '13 at 01:37

4 Answers4

6

The beauty of breadth-first search is that it will automatically find the shortest path (you just need to keep track of where you came from when you visit a node). With a breadth-first search, you always have the cheapest paths at the beginning of the queue and the expensive ones at the end. As soon as you hit your goal P, you are guaranteed that the path length is minimal.

An std::queue is an absolutely fine choice for implementing it.

In response to your comment: You have a queue of nodes / vertices (in your case, these are your cells). When you visit a node, you add all neighbours that you haven't previously visited to the queue. To keep track of which nodes you have visited and where your paths came from, keep an std::array/std::vector wherefrom; around, with one element for each of your nodes. Then (pseudocode!)

take element v from queue
 for each neighbour x of v
    if wherefrom[x] != NULL
     wherefrom[x] = v
     add x to end of queue

Once you hit your target node P, you can just backtrack through wherefrom to find the path.

us2012
  • 16,083
  • 3
  • 46
  • 62
  • 1
    Why use `std::deque` over the wrapped version `std::queue`? – templatetypedef Jan 30 '13 at 01:31
  • But when examining the queue, if we run into a path that leads nowhere, what do we do with that path? In other words, where is the "final path" stored so that it's easily accessible once the algorithm has finished? What implementation techniques can be used to make this run fast on large inputs? – Bob John Jan 30 '13 at 01:36
  • I'm sorry, I'm still slightly confused. There are multiple paths searched by the algorithm, so my question is how do you determine what is "the" path when the algorithm is finished? Certainly it isn't all the positions popped from the queue, so what systematic method can be used to store the locations (as the algorithm is running) then determine the final path (when the algorithm is done). I'm sorry if I'm not understanding something obvious, but this is where my confusion lies. – Bob John Jan 30 '13 at 02:33
  • 1
    @BobJohn [See A*](http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode) (I know you want to "make your own", but check out the pseudocode and the explanation in the rest of the article). See the section below on the requirements for the heuristic - e.g. that there is no "warp gate" at any node. Also consider when the heuristic *always* returns 0 (this is Djikstra's). –  Jan 30 '13 at 02:50
3

I would advise that you read up on Dijkstra's algorithm, and then progress to A* search.

Here is a simple way to solve this problem in C++:

  1. Create a std::vector of ints (let's call it "trail") initialized to -1, with one element for each node in your map (size 25 in your example). This will be used to indicate which nodes have already been searched, and where they have been searched from. A node with a 'trail' value of -1 has not been searched, and a node with 'trail' value 8 has been searched from node 8.

  2. Create a std::queue of ints (let's call it "search_queue"). Then push the ID of the node containing 'A', and mark its 'trail' value to itself. E.g. if 'A' is node 20, then set trail[20] to 20; This records that the trail started at that point.

  3. Pop the front node from 'search_queue', and look at each its neighbors in turn, adding their id to the queue if their trail value is -1, and they are not restricted (do not contain '|').

  4. Repeat step 3 until you find 'P' (you reached the goal!), or the queue runs empty (there is no valid path).

  5. If you found 'P', then trace your path back to the beginning using your 'trail' vector -- each node will point to the previous node in the path, until you reach a node that points to itself. That is where you started, so you now have a complete path!

You don't have to calculate any distances, because the nature of breath-first-search guarantees that the first valid path that the algorithm finds will be the shortest one possible.

David
  • 51
  • 4
2

I assume you have a two-dimensional array with A P O | values. If unknown, you will need to find A using brute force searching.

For paths, the shortest path from A can be found by creating a set of 1-move positions (i.e. above, right, and possible above-right if diagonal moves are allowed). As you do so, you want to track which positions have been visited to avoid returning to the same square, so you either need to do something to the original array (e.g. change visited positions from "O" to "o") or have another array just for this. From the 1-move position, you can create the set of legal 2-move positions that haven't already been visited. Keep going until you find "P".

Regarding choice of container: with the algorithm above you're not popping anything - can just use a vector.

As a optimisation, you may want to local P too and try a depth-first traversal of the most obvious paths between the two - in your illustated case [diagonally-up-right-]-else-up-else-right with "up" allowed until you reach the target row, and "right" until you reach the column. Could do right-else-up too or instead.

Tony Delroy
  • 102,968
  • 15
  • 177
  • 252
0

Once you have the map:

O O P O |
O O O O O
O | O | O
O O O O O
A O O O O

define the graph, 1 indicates if there is an edge:

1 1 P 1 0
1 1 1 1 1
1 0 1 0 1
1 1 1 1 1
A 1 1 1 1

where a_ij = 0 iff m_ij = | and elsewhere a_ij = 1

then run Dijkstra's algorithm or Bellman-ford algorithm.

If you insist to use BFS, here is an explanation why it works as well:

How does a Breadth-First Search work when looking for Shortest Path?

Community
  • 1
  • 1
0x90
  • 39,472
  • 36
  • 165
  • 245