CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3
  1. #1
    Join Date
    Oct 2009
    Posts
    1

    Question 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)

  2. #2
    Join Date
    May 2009
    Location
    Boston
    Posts
    364

    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.

  3. #3
    Join Date
    May 2009
    Posts
    2,413

    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
  •  





Click Here to Expand Forum to Full Width

Featured