# Rat in a maze problem

Discussion in 'C++' started by NK, Jun 28, 2007.

1. ### NKGuest

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

NK, Jun 28, 2007

2. ### Kai-Uwe BuxGuest

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

Kai-Uwe Bux, Jun 28, 2007

3. ### =?ISO-8859-1?Q?Erik_Wikstr=F6m?=Guest

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

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=, Jun 28, 2007
4. ### Juha NieminenGuest

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.

Juha Nieminen, Jun 28, 2007
5. ### Fei LiuGuest

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

Fei Liu, Jun 29, 2007