473,888 Members | 1,276 Online

# Recursive algoritme for finding the shortest path

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_n ext_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 :-(?
Jul 22 '05 #1
20 17060

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
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_n ext_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

Jul 22 '05 #2
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
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_n ext_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

Jul 22 '05 #3

"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?
Jul 22 '05 #4

"Webdad" <No**********@p andora.be> schrieb im Newsbeitrag
news:0H******** ************@ph obos.telenet-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 ...

-> 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_n ext_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<PIXE L> pixels;
pixels.push(PIX EL(x,y));
while(pixels.si ze())
{
PIXEL px = pixels.top;
pixels.pop();
if(!data[px.x][px.y])
{
data[px.x][px.y]=1;
pixels.push(PIX EL(px.x-1, px.y));
pixels.push(PIX EL(px.x+1, px.y));
pixels.push(PIX EL(px.x, px.y-1));
pixels.push(PIX EL(px.x, px.y+1));
}
}
}

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

-Gernot

Jul 22 '05 #5

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!

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

--
Karl Heinz Buchegger
Jul 22 '05 #6

"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 ...
Jul 22 '05 #7
"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 ...
Jul 22 '05 #8
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<PIXE L> pixels;
pixels.push(PIX EL(x,y));
while(pixels.si ze())
{
PIXEL px = pixels.top;
pixels.pop();
if(!data[px.x][px.y])
{
data[px.x][px.y]=1;
pixels.push(PIX EL(px.x-1, px.y));
pixels.push(PIX EL(px.x+1, px.y));
pixels.push(PIX EL(px.x, px.y-1));
pixels.push(PIX EL(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
Jul 22 '05 #9
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

Jul 22 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.