CODEWITHSUNDEEP
c++algorithmsearch
Bob John
Bob John

Reputation: 3878

How can you use a breadth-first search to find the shortest path in a map?

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?

Upvotes: 2

Views: 13687

Answers (4)

David
David

Reputation: 51

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.

Upvotes: 3

Tony Delroy
Tony Delroy

Reputation: 106096

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.

Upvotes: 2

us2012
us2012

Reputation: 16253

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.

Upvotes: 6

0x90
0x90

Reputation: 40982

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?

Upvotes: 0

Related Questions