473,888 Members | 1,276 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 ...

(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_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

Webdad wrote:
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_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
Webdad wrote:
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_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 ...

(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_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.

instead of:
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
Webdad wrote:

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
kb******@gascad .at
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]
instead of:
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
kb******@gascad .at
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.

Similar topics

4
4734
by: Porthos | last post by:
Hi All, I'm trying to find the minimum value of a set of data (see below). I want to compare the lengths of these attribute values and display the lowest one. This would be simple if I could re-assign values to a variable, but from what I gather I can't do that. How do I keep track of the lowest value as I loop through? My XSL document only finds the length of each string and prints it out (for now). I can write a template
6
2104
by: Lau | last post by:
How do I easily calculate the shortest path between two geographical spots on a map? The map is divided into zones. So I guess it is possible to use Dijkstra’s Shortest Path algorithm, but it seems like a lot of work and I am sure that it has been done many times before. From (x,y) coordinates I need to place the user in a zone and find the shortest path to all other zones. Any suggestions are more than welcome. I would hate to reinvent...
6
5890
by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not parse then it takes about O(N^2) where N is the # of vertices, too much for large graphs. Furthermore, I don't need to know the all the path from a start point to every other single vertex as Dijkstra would provide. Just the shortest path from a...
4
3722
by: Elmo Watson | last post by:
Is there a way, with the System.IO class, to do a recursive list of a directory structure? For instance, in DirectoryInfo, you have GetDirectories and GetFiles .... In Directory, you have Directory.GetFileSystemEntries(path), but I would like to know how to put this together, knowing which entry is a Subdirectory and which entry is a file, and make a recursive list of the Directory structure below a specific path - - -
5
7402
by: leezard | last post by:
I am developing a program using VB.NET that will accept a start and end point, the system then will generate the shortest path to reach the end point. Anyone here have idea on doing this or some code examples that can share it with me? Thanks in advance.
5
2888
by: costantinos | last post by:
Hello. I have implemented the Dijkstra shortest path algorithm, it works fine but I have one question on how I can improve something. I want to find all the possible shortest paths from a node since there is a possibility to exist more than one shortest paths with the same distance. Does anyone has any idea how this could be done? Code
2
3108
by: Bytter | last post by:
Hi everyone, I need to implement a very quick (performance-wise) Dijkstra shortest path in python, and found that libboost already has such thing. Problem is: I cannot find the installation package for my Python 2.4 under windows. Can someone please provide me instructions for installing libboost for python? In alternative, if someone can point out to a fast Dijkstra shortest path in python (the network is over 1 million vertexes), I...
5
2418
by: aleya | last post by:
I am developing a program using VB.NET that will accept a start and end location (2 list boxes), the system then will generate the shortest path to reach the end point. for your information i got a code in C and succesfully translated it into vb.net. however this code had fix the length during the declaration. what i want to do now is keep the distances in database (sql server) and during calculation it'll retrieve data from database.i had...
9
2649
by: pereges | last post by:
Hello I need some ideas for designing a recursive function for my ray tracing program. The idea behind ray tracing is to follow the electromagnetic rays from the source, as they hit the object.The object is triangulated. The rays can undergo multiple reflections, diffractions etc of the same object i.e. a ray hits a surface of the object, undergoes reflection resulting in a reflected ray which can again hit a surface, corner or edge...
0
9961
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9800
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11186
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10778
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10887
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
10439
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
1
7990
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
7148
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
1
4642
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.