Velocity Reviews > C++ > Rat in a maze problem

# Rat in a maze problem

NK
Guest
Posts: n/a

 06-28-2007
Rat in a Maze pblm can be solved using Stack data structure but
shortest possible path can't be found using it(but we can found a
possible path).To find shortest possible path without calculating
length of path which data struc. should be used .plz also describe
algo to solve it.

we can find all possible path using Stack..... then calculate length
of each possible path and find shortest one but its very time and
space consuming soln.

Thanks

NK

Kai-Uwe Bux
Guest
Posts: n/a

 06-28-2007
NK wrote:

> Rat in a Maze pblm can be solved using Stack data structure but
> shortest possible path can't be found using it(but we can found a
> possible path).To find shortest possible path without calculating
> length of path which data struc. should be used .plz also describe
> algo to solve it.
>
>
> we can find all possible path using Stack..... then calculate length
> of each possible path and find shortest one but its very time and
> space consuming soln.

a) This is not a language question but an algorithm question. You are better
off in a group like comp.programming. Once you run into trouble wording the
solution in C++, this news group would be appropriate.

b) The problem sounds like homework. People will be more inclined to help
you if they can see that you made an honest effort to solve it yourself.

c) Your problem looks like finding shortest distances in graphs (possibly
with edged of lengths != 1). Read up on graph algorithms (a library is your
friend, if all else fail, there is Google). You are bound to find tons of
ideas. Also, the problem would benefit from a little clarification: are you
interested in the shortest path between two particular points or do you
want to compile a shortest distance table for the whole graph?

Best

Kai-Uwe Bux

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=
Guest
Posts: n/a

 06-28-2007
On 2007-06-28 08:25, NK wrote:
> Rat in a Maze pblm can be solved using Stack data structure but
> shortest possible path can't be found using it(but we can found a
> possible path).To find shortest possible path without calculating
> length of path which data struc. should be used .plz also describe
> algo to solve it.
>
>
> we can find all possible path using Stack..... then calculate length
> of each possible path and find shortest one but its very time and
> space consuming soln.

Please, try to write the whole words instead of a lot of pblms and plz,
it makes your post much harder to read an it does not save you any
significant amount of time.

Anyway, it sounds to me like a general shortest path problem, and there
are a number of ways to solve these, use google.

--
Erik Wikström

Juha Nieminen
Guest
Posts: n/a

 06-28-2007
NK wrote:
> Rat in a Maze pblm can be solved using Stack data structure but
> shortest possible path can't be found using it

I don't think that's true, unless you mean a "pure" stack which
has *only* the operations "push" and "pop" and no random acccess.

You should use google. Try with "breadth first".

Fei Liu
Guest
Posts: n/a

 06-29-2007
NK wrote:
> Rat in a Maze pblm can be solved using Stack data structure but
> shortest possible path can't be found using it(but we can found a
> possible path).To find shortest possible path without calculating
> length of path which data struc. should be used .plz also describe
> algo to solve it.
>
>
> we can find all possible path using Stack..... then calculate length
> of each possible path and find shortest one but its very time and
> space consuming soln.
>
> Thanks
>
>
> NK
>

understanding graph shortest path algorithm + boost::graph = win

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post pleatofthepants C++ 1 03-03-2008 07:21 AM szewong@gmail.com Java 0 05-10-2007 06:59 PM Fastmoggy Computer Support 1 01-09-2007 07:55 PM Adam Knight ASP .Net 15 11-02-2005 07:35 AM Dave - Dave.net.nz NZ Computing 0 10-31-2004 11:40 PM

Advertisments