Velocity Reviews > C++ > Recursive algoritme for finding the shortest path

# Recursive algoritme for finding the shortest path

Guest
Posts: n/a

 12-07-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 ?

msalters
Guest
Posts: n/a

 12-07-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 ...
>
> (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/...ry_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
Guest
Posts: n/a

 12-07-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 ...
>
> (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/...ry_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

Guest
Posts: n/a

 12-07-2004

"msalters" schreef:

> www.boost.org has the graph library, which contains this algorithm:
> http://www.boost.org/libs/graph/doc/...ry_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?

Gernot Frisch
Guest
Posts: n/a

 12-07-2004

"Webdad" <(E-Mail Removed)> schrieb im Newsbeitrag
news:0Hitd.12552\$(E-Mail Removed)-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

Karl Heinz Buchegger
Guest
Posts: n/a

 12-07-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 ...
>
> (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
http://www.velocityreviews.com/forums/(E-Mail Removed)

Jochus
Guest
Posts: n/a

 12-07-2004

"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
Guest
Posts: n/a

 12-07-2004
"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 ...

Karl Heinz Buchegger
Guest
Posts: n/a

 12-07-2004
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
(E-Mail Removed)

Dave O'Hearn
Guest
Posts: n/a

 12-07-2004
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