Shortest Path - Breadth first search

Question

I have an assignment for a paper and in no means am I asking for any code help, only help to understand how to approach this problem.

We where given minimal material to work from and the professor only skimmed over the content of Breadth first search.

We need to find our way through a maze, the maze is is created and your person lands on a random space every time.

When the key is pressed the current position is sent to the function and from there we have to use breadth first search to find the shortest path.

Now what I understand from this search algorithm is the following:

Tree or graph must be searched in levels
We need to store the paths in a queue (FIFO)
Then find the shortest path out of all paths to the end item

How exactly do I approach this type of problem?

We know the start and end, plus we can get all the neighbour blocks of the current block easily.

Much appreciated.

If you're not asking for help with code then you came to the wrong site. — dursk
Hi @dursk thanks for your contribution but I do believe that it's quite ok to ask this question here. — Tiaan Swart
The python flag relates to the link provided and was suggested by StackExchange :) — Tiaan Swart

moreON moreON · Accepted Answer · 2015-10-19T05:58:40

You seem to have missed some nuance of Breadth first search.

Tree or graph must be searched in levels

This is correct. Although you won't necessarily keep track of a set of distinct levels, you just naturally continue to the next one after one is completed.

We need to store the paths in a queue (FIFO)

Not really. You typically store future nodes to explore in a queue, not entire paths. Maintaining the path, if required is an extra problem.

Then find the shortest path out of all paths to the end item

In a graph that has uniform edge weights, this is unnecessary. The first path you find is the shortest. (Do note the requirement of uniform edge weights for this to be true for BFS)

The general code for a BFS for a goal node is something like the following:

q := new Queue
q.enqueue(start)
goal_found := false
while( q is not empty )
    n := q.dequeue()
    if n is goal then
        goal_found := true
        break
    for each neighbour v of n
        q.enqueue(v)

if(goal_found)
    //do something (success)
else
    //do something else (failure)

There is a little more to add to this skeleton if you wish to track the path you traversed, prevent doubling back on your path (in an undirected graph this is very important for ensuring termination), prevent repeat processing of a node in general (necessary if there are cycles and you want to terminate), keep track of length, etc. But this is the basic framework for it.

Shortest Path - Breadth first search

1 Answers