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.
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.
Last edited by LMHmedchem; October 5th, 2009 at 04:06 PM.