-
October 5th, 2009, 01:29 PM
#1
problem with breadth first search
how do i implement breadth first search using a queue to find the shortest path from the upper left corner to the lower right corner, if there is one.A path can only go up, down, or sideways (not diagonally) and must only pass through zeros. The ones are walls. The number of rows will not exceed 40, and the number of columns will not exceed 78. if im not being clear this is an example.
input:
3 5
01000
00010
01010
output:
01000
00010
01010
( 1, 1)( 2, 1)( 2, 2)( 2, 3)( 1, 3)( 1, 4)( 1, 5)( 2, 5)( 3, 5)
-
October 5th, 2009, 04:01 PM
#2
Re: problem with breadth first search
Most graph search algorithms are based on a connection table. It is a bit unclear as to where the vertices and edges are in your example. I think you need to start by abstracting a connection table from your input, after that point is should be easy. cpp has a number of graph library functions, if you are planning on using them, make sure that the format of the connection table you develop is in the same form as the expected input to the std graph functions. That will save you having to create an abstraction to translate.
It also seems as if you would want a depth-first search, or a hybrid. The simple way is to find all paths and then just count to see what the shortest is. Otherwise you need to develop a cost metric for deciding which path to follow when there is more than one choice.
LMHmedchem
Last edited by LMHmedchem; October 5th, 2009 at 04:06 PM.
-
October 5th, 2009, 04:05 PM
#3
Re: problem with breadth first search
http://en.wikipedia.org/wiki/Breadth-first_search
If you tell me the name of the course and year in curriculum, I may give you more.
Last edited by nuzzle; October 5th, 2009 at 07:18 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|