Rat in a maze problem

[NK]

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]

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?=]

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]

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]

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