# Recursive algoritme for finding the shortest path

Discussion in 'C++' started by Webdad, Dec 7, 2004.

Hi!

I running my first year as industrial engineer (informatics)

We have an assignment to do :
.... create a playfield (matrix[DIM][DIM]). Some places in that field are
blocked, so you can't pass them. The others are free to go over ...

-> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp

Now I need the find an algoritme to find the shortest way between to random
points in that field. I have a a lot possibilities ... But some are blocked
(because you can't pass them) ... Some are way too long!

This should be the algoritme:

for the four possibilities (east, south, west, north) {
if step is possible {// when you don't leave the playfield
make new point // execute step
distance = distance_from_next_point +1
if distance is'n't know in the new point OR distance is
smaller then distance {
remember distrance for new point
make step from new point
}
}
}

This is Pseudo code ... But I can't find the code in C++. It should be a
recursive one ... Who can help me out :-(?

2. ### msaltersGuest

> Hi!
>
> I running my first year as industrial engineer (informatics)
>
> We have an assignment to do :
> ... create a playfield (matrix[DIM][DIM]). Some places in that field

are
> blocked, so you can't pass them. The others are free to go over ...
>
> (I already found that part)
> -> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp

Well, you probably need to have a word with your tutor about the
quality of his C++ course. You shouldn't be dealing with arrays.

> Now I need the find an algoritme to find the shortest way between to

random
> points in that field. I have a a lot possibilities ... But some are

blocked
> (because you can't pass them) ... Some are way too long!
>
> This should be the algoritme:
>
> for the four possibilities (east, south, west, north) {
> if step is possible {// when you don't leave the playfield
> make new point // execute step
> distance = distance_from_next_point +1
> if distance is'n't know in the new point OR distance

is
> smaller then distance {
> remember distrance for new point
> make step from new point
> }
> }
> }

Sounds like the Dijkstra algorithm, special case with all distances are
+1.
www.boost.org has the graph library, which contains this algorithm:
http://www.boost.org/libs/graph/doc/graph_theory_review.html
Sounds like you can use Breadth-First Search.

Of course, using boost::graph may be somewhat harder than coding it
yourself, for such a simple case.

Regards,
Michiel Salters

msalters, Dec 7, 2004

3. ### msaltersGuest

> Hi!
>
> I running my first year as industrial engineer (informatics)
>
> We have an assignment to do :
> ... create a playfield (matrix[DIM][DIM]). Some places in that field

are
> blocked, so you can't pass them. The others are free to go over ...
>
> (I already found that part)
> -> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp

Well, you probably need to have a word with your tutor about the
quality of his C++ course. You shouldn't be dealing with arrays.

> Now I need the find an algoritme to find the shortest way between to

random
> points in that field. I have a a lot possibilities ... But some are

blocked
> (because you can't pass them) ... Some are way too long!
>
> This should be the algoritme:
>
> for the four possibilities (east, south, west, north) {
> if step is possible {// when you don't leave the playfield
> make new point // execute step
> distance = distance_from_next_point +1
> if distance is'n't know in the new point OR distance

is
> smaller then distance {
> remember distrance for new point
> make step from new point
> }
> }
> }

Sounds like the Dijkstra algorithm, special case with all distances are
+1.
www.boost.org has the graph library, which contains this algorithm:
http://www.boost.org/libs/graph/doc/graph_theory_review.html
Sounds like you can use Breadth-First Search.

Of course, using boost::graph may be somewhat harder than coding it
yourself, for such a simple case.

Regards,
Michiel Salters

msalters, Dec 7, 2004

"msalters" schreef:

> www.boost.org has the graph library, which contains this algorithm:
> http://www.boost.org/libs/graph/doc/graph_theory_review.html
> Sounds like you can use Breadth-First Search.
>
> Of course, using boost::graph may be somewhat harder than coding it
> yourself, for such a simple case.

Hmm, I looked the site very closefully ... But it's rather hard to
understand for a newbie as me ...
Maybe arrays aren't so good, but what would you take in mind?

5. ### Gernot FrischGuest

news:0Hitd.12552\$-ops.be...
> Hi!
>
> I running my first year as industrial engineer (informatics)
>
> We have an assignment to do :
> ... create a playfield (matrix[DIM][DIM]). Some places in that field
> are
> blocked, so you can't pass them. The others are free to go over ...
>
> (I already found that part)
> -> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp
>
> Now I need the find an algoritme to find the shortest way between to
> random
> points in that field. I have a a lot possibilities ... But some are
> blocked
> (because you can't pass them) ... Some are way too long!
>
> This should be the algoritme:
>
> for the four possibilities (east, south, west, north) {
> if step is possible {// when you don't leave the playfield
> make new point // execute step
> distance = distance_from_next_point +1
> if distance is'n't know in the new point OR distance
> is
> smaller then distance {
> remember distrance for new point
> make step from new point
> }
> }
> }
>
> This is Pseudo code ... But I can't find the code in C++. It should
> be a
> recursive one ... Who can help me out :-(?

Do _not_ do such algorithms recursively - it's gonna go stack overflow
in the last test before shipping the release version, believe me.

void Fill(int x, int y)
{
if(data[x][y]) return;
data[x][y]=1;
Fill(x-1, y); Fill(x+1,y); Fill(x,y-1); Fill(x,y+1);
}

do this:

struct PIXEL
{
int x,y;
};

void Fill(int x, int y)
{
std::stack<PIXEL> pixels;
pixels.push(PIXEL(x,y));
while(pixels.size())
{
PIXEL px = pixels.top;
pixels.pop();
if(!data[px.x][px.y])
{
data[px.x][px.y]=1;
pixels.push(PIXEL(px.x-1, px.y));
pixels.push(PIXEL(px.x+1, px.y));
pixels.push(PIXEL(px.x, px.y-1));
pixels.push(PIXEL(px.x, px.y+1));
}
}
}

see what I mean? Use a dynamic stack instead of recurs(e)ion.

-Gernot

Gernot Frisch, Dec 7, 2004
6. ### Karl Heinz BucheggerGuest

>
> Hi!
>
> I running my first year as industrial engineer (informatics)
>
> We have an assignment to do :
> ... create a playfield (matrix[DIM][DIM]). Some places in that field are
> blocked, so you can't pass them. The others are free to go over ...
>
> (I already found that part)
> -> http://users.pandora.be/hebbrecht/jochen/c++/test.cpp
>
> Now I need the find an algoritme to find the shortest way between to random
> points in that field. I have a a lot possibilities ... But some are blocked
> (because you can't pass them) ... Some are way too long!

Search the web for 'Lee algorithm'.
Once you understand it, it is easy to implement.

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 7, 2004
7. ### JochusGuest

"Gernot Frisch" schreef:

> Do _not_ do such algorithms recursively - it's gonna go stack overflow
> in the last test before shipping the release version, believe me.

Yes, I know ... But that is the thing we are learning. For large fields,
it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
I'm afraid he will disagree and say I have to use his solution ...

Jochus, Dec 7, 2004
8. ### JochusGuest

"Jochus" schreef:

> Yes, I know ... But that is the thing we are learning. For large fields,
> it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
> I'm afraid he will disagree and say I have to use his solution ...

Btw, this is my account ... This noon, I was using my dad's account ...

Jochus, Dec 7, 2004
9. ### Karl Heinz BucheggerGuest

Gernot Frisch wrote:
>

[snip]

> void Fill(int x, int y)
> {
> if(data[x][y]) return;
> data[x][y]=1;
> Fill(x-1, y); Fill(x+1,y); Fill(x,y-1); Fill(x,y+1);
> }
>
> do this:
>
> struct PIXEL
> {
> int x,y;
> };
>
> void Fill(int x, int y)
> {
> std::stack<PIXEL> pixels;
> pixels.push(PIXEL(x,y));
> while(pixels.size())
> {
> PIXEL px = pixels.top;
> pixels.pop();
> if(!data[px.x][px.y])
> {
> data[px.x][px.y]=1;
> pixels.push(PIXEL(px.x-1, px.y));
> pixels.push(PIXEL(px.x+1, px.y));
> pixels.push(PIXEL(px.x, px.y-1));
> pixels.push(PIXEL(px.x, px.y+1));
> }
> }
> }
>
> see what I mean? Use a dynamic stack instead of recurs(e)ion.
>

Use a different algorithm
The above is not even close to what the OP is lookin for.

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 7, 2004
10. ### Dave O'HearnGuest

msalters wrote:
> Sounds like the Dijkstra algorithm, special case with all
> distances are +1.

I thought it looked like a weird Depth-First Search that relaxes edges.
Off hand, I have no idea whether such a thing would work or not.
Whatever it is, it's apparently recursive, yet finds shortest paths.

In any case, there is not much luck of the original poster finding
source code that does this online, if he is stuck using this bizarre
algorithm. The first place to start would be to find out the name of
the algorithm, if it has a name.

--
Dave O'Hearn

Dave O'Hearn, Dec 7, 2004
11. ### Dave O'HearnGuest

msalters wrote:
> Sounds like the Dijkstra algorithm, special case with all
> distances are +1.

I thought it looked like a weird Depth-First Search that relaxes edges.
Off hand, I have no idea whether such a thing would work or not.
Whatever it is, it's apparently recursive, yet finds shortest paths.

In any case, there is not much luck of the original poster finding
source code that does this online, if he is stuck using this bizarre
algorithm. The first place to start would be to find out the name of
the algorithm, if it has a name.

--
Dave O'Hearn

Dave O'Hearn, Dec 7, 2004
12. ### Dave O'HearnGuest

msalters wrote:
> Sounds like the Dijkstra algorithm, special case with all
> distances are +1.

I thought it looked like a weird Depth-First Search that relaxes edges.
Off hand, I have no idea whether such a thing would work or not.
Whatever it is, it apparently uses a stack (recursion) to find shortest
paths.

In any case, there is not much luck of the original poster finding
useful resources, if he is stuck using this bizarre algorithm. The
first place to start would be to find out the name of the algorithm, if
it has a name.

--
Dave O'Hearn

Dave O'Hearn, Dec 7, 2004
13. ### Karl Heinz BucheggerGuest

Jochus wrote:
>
> "Gernot Frisch" schreef:
>
> > Do _not_ do such algorithms recursively - it's gonna go stack overflow
> > in the last test before shipping the release version, believe me.

>
> Yes, I know ... But that is the thing we are learning. For large fields,
> it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
> I'm afraid he will disagree and say I have to use his solution ...

So what *is* his solution.

The recursion is quite easy to do. Let us forget for the *shortest*
path for the moment. Just concenrate on *a* path.
BTW: The whole concept is called backtracking. I usually gave my
students a variation of your assignment, called: "How the mouse gets
the cheese": There is a labyrinth in a 2D array. Each array element
is marked as beeing either:
* empty space (' ')
* a wall ('*')
* the mouse ('M')
* the cheese ('C')
The goal is to find (using backtracking) a path from the mouse to
the chesse. As said: If you know backtrakcking this is quite simple
to do. Once that part runs, it is easy to generalize it such that the
shortest path can be found.
I will use that assignment in the discussion, since I don't want to do

As most of the time with recursion you first have to think of a few
things. First you need to a global understanding of what your function
has to do:
Given a coordinate in the array (2 indices), find a way from that position
to the goal.

Plain and simple.

Next you should think about the trivial case. That is: When is this problem
so easy, that a solution can be given immediatly?
In the above example, the answer is (don't laugh it really is that trivial),
"When the coordinates already hold the cheese." In this case you found a
solution.

Are there any other trivial cases?
Yes, sure. When there is a wall at the position in question. Obviously the cheese
cannot be at this position. In this case case the search failed (for that position).

And in the other - non trivial - cases: Well, just try if the position to the north
leads to the chesse. If it does, fine you found a solution. The position in question
is part of that solution. If it does not, try to the south. If solution ....
If not, try west .... If not try east.

And that's it, for just one small detail: The mouse needs to keep track of what
positions it already tried, such that it will never try the same position again.
How is that done: Simple: just mark the array element with some character, lets
say a '.'. So we have one more trivial case: When the searched position contains
a '.' the search failed for that position, because the mouse had visited that

bool Search( int IndX, int IndY )

That is: search the maze at position IndX/IndY for the cheese.
The return value will either be true or false, depending if the
cheese was found or not.

Now filling in what we already know from the above:

bool Search( int IndX, int IndY )
{
// Trivial case 1:
// if that position contains the cheese: hurra

if( Maze[IndY][IndX] == 'C' ) {
cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
return true;
}

// Trivial case 2:
// if that position contains a wall: sniff, the cheese cannot be here
if( Maze[IndY][IndX] == '*' )
return false;

// Trivial case 3:
if( Maze[IndY][IndX] == '.' )
return false;

// The mouse entered empty space, try north south, east, west
// If one of those searches leads to the chesse: fine
//
// But first mark that the mouse entered this field already:
Maze[IndY][IndX] = '.';

if( Search( IndX, IndY + 1 ) ||
Search( IndX, IndY - 1 ) ||
Search( IndX - 1, IndY ) ||
Search( IndX + 1, IndY ) ) {
cout << "Path " << IndX << " " << IndY << endl;
return true;
}

// sniff: The cheese is not at position IndX/IndY and a search
// to the north/south/east/west didn't come up with the cheese
// report failure to caller

return false;
}

and that's it.

A quick test program reveals:

#include <iostream>
using namespace std;

char Maze[7][16] = { "***************",
"* C * *",
"****** * *** **",
"* * * **",
"* ****** * ** *",
"* * * *",
"***************" };

bool Search( int IndX, int IndY )
{
.... See above
}

int main()
{

if( Search( 11, 3 ) )
cout << "Cheese found" << endl;
else
}

Step it through with your debugger until you clearly
understand how everything works. It might also be a
good idea to insert additional output statements
into Search: eg.

bool Search( int IndX, int IndY )
{
cout << "Testing position " << IndX << " " << IndY << "\n";

// Trivial case 1:
// if that position contains the cheese: hurra

if( Maze[IndY][IndX] == 'C' ) {
cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
return true;
}

// Trivial case 2:
// if that position contains a wall: sniff, the cheese cannot be here
if( Maze[IndY][IndX] == '*' ) {
cout << "Hit a wall!\n";
return false;
}

....

Another hint: In your first attempts to follow the program flow in your
debugger, make sure the mouse starts near the cheese! Eg. a position
4 1 would be a good candiate.

Once you understand, how the mouse gets to the cheese, apply what you
have learned to your real problem. But: First make your program search
any path, then concentrate on letting it search for the shortest path!

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 7, 2004
14. ### Karl Heinz BucheggerGuest

Karl Heinz Buchegger wrote:
>

Oh and by the way:
Look up 'backtracking'.
It is a mighty concept of beeing lazy: Test if
the goal is reached, if yes - fine, if not recurse
and try a variation. In fact the whole 'backtracking'
concept is nothing more then a clever ordered search
strategy through the whole solution space.

There are lots of other classical assignments for
backtracking: 8-queens, knapsack, stable marriage, ....

And yes, I expect every serious programmer to be able
to apply backtracking.

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 7, 2004
15. ### JochusGuest

"Karl Heinz Buchegger" schreef:

> So what *is* his solution.
>
> The recursion is quite easy to do. Let us forget for the *shortest*
> path for the moment. Just concenrate on *a* path.
> BTW: The whole concept is called backtracking. I usually gave my
> students a variation of your assignment, called: "How the mouse gets
> the cheese": There is a labyrinth in a 2D array. Each array element
> is marked as beeing either:
> * empty space (' ')
> * a wall ('*')
> * the mouse ('M')
> * the cheese ('C')
> The goal is to find (using backtracking) a path from the mouse to
> the chesse. As said: If you know backtrakcking this is quite simple
> to do. Once that part runs, it is easy to generalize it such that the
> shortest path can be found.
> I will use that assignment in the discussion, since I don't want to do

>8 SNIP 8<

Wow, thnx for all that typework! I read it and it soo much better to
understand ... But my teacher wants it to do like this:

for the four possibilities (east, south, west, north) {
if step is possible {// when you don't leave the playfield
make new point // execute step
distance = distance_from_next_point +1
if distance is'n't know in the new point OR distance is
smaller then distance {
remember distrance for new point
make step from new point
}
}
}

It must hold something like this ... But it's hard to program :-( ... As I
don't understand what this function would do....

Jochus, Dec 7, 2004
16. ### Karl Heinz BucheggerGuest

Jochus wrote:
>
> "Karl Heinz Buchegger" schreef:
>
> > So what *is* his solution.
> >
> > The recursion is quite easy to do. Let us forget for the *shortest*
> > path for the moment. Just concenrate on *a* path.
> > BTW: The whole concept is called backtracking. I usually gave my
> > students a variation of your assignment, called: "How the mouse gets
> > the cheese": There is a labyrinth in a 2D array. Each array element
> > is marked as beeing either:
> > * empty space (' ')
> > * a wall ('*')
> > * the mouse ('M')
> > * the cheese ('C')
> > The goal is to find (using backtracking) a path from the mouse to
> > the chesse. As said: If you know backtrakcking this is quite simple
> > to do. Once that part runs, it is easy to generalize it such that the
> > shortest path can be found.
> > I will use that assignment in the discussion, since I don't want to do

>
> >8 SNIP 8<

>
> Wow, thnx for all that typework! I read it and it soo much better to
> understand ... But my teacher wants it to do like this:
>
> for the four possibilities (east, south, west, north) {
> if step is possible {// when you don't leave the playfield
> make new point // execute step
> distance = distance_from_next_point +1
> if distance is'n't know in the new point OR distance is
> smaller then distance {
> remember distrance for new point
> make step from new point
> }
> }
> }
>
> It must hold something like this ... But it's hard to program :-( ... As I
> don't understand what this function would do....

Study what I posted. Test it, run it, until you finally understand how
it works. (It is really the same concept). Then apply what you

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 7, 2004
17. ### JochusGuest

"Karl Heinz Buchegger" schreef:

> Study what I posted. Test it, run it, until you finally understand how
> it works. (It is really the same concept). Then apply what you
> have learned to your problem.

Hmm, yes ... But am I wrong when I say that your solution isn't a
utilization on recursive methodes?

That's what this assignment holds on! Recursive functions ... Like
calculating faculties ... or "The Towers of Hanoi".

Jochus, Dec 7, 2004
18. ### Gernot FrischGuest

> Use a different algorithm
> The above is not even close to what the OP is lookin for.

I just wanted to explain how to replace recursion - using a very
simple example.
BTW. Your cheese-mouse example was nice.
-Gernot

Gernot Frisch, Dec 8, 2004
19. ### JochusGuest

"Gernot Frisch" schreef:

> I just wanted to explain how to replace recursion - using a very
> simple example.

I spoke to my teacher: we MUST use recursion ... He agrees it isn't the best
solution, but it's good to learn us recursion...

The idea of mouse & cheese: he doesn't agree because it's an example on
backtracing ... I can't use that example ...

Jochus, Dec 8, 2004
20. ### Karl Heinz BucheggerGuest

Jochus wrote:
>
> "Karl Heinz Buchegger" schreef:
>
> > Study what I posted. Test it, run it, until you finally understand how
> > it works. (It is really the same concept). Then apply what you
> > have learned to your problem.

>
> Hmm, yes ... But am I wrong when I say that your solution isn't a
> utilization on recursive methodes?
>
> That's what this assignment holds on! Recursive functions ... Like
> calculating faculties ... or "The Towers of Hanoi".

Study it. The function is only 17 lines long (excluding comments).
There are *4* recursive calls!

--
Karl Heinz Buchegger

Karl Heinz Buchegger, Dec 9, 2004