Re: Shortest Path Problem
- To: mathgroup at smc.vnet.net
- Subject: [mg96373] Re: [mg96293] Shortest Path Problem
- From: DrMajorBob <btreat1 at austin.rr.com>
- Date: Thu, 12 Feb 2009 06:39:25 -0500 (EST)
- References: <200902111018.FAA16939@smc.vnet.net>
- Reply-to: drmajorbob at longhorns.com
I agree the documentation on ShortestPath is execrable. Extremely so.
But your description of the problem isn't much better.
For a shortest path problem, first you need points. But how many are there?
10?
10+10 for the rows and columns?
Or 10*10=100 for all the grid entries?
Tell me how many points there are, and we could begin to draw a graph,
solve a shortest path problem, or whatever.
Next you need the distance from one point to another. It makes sense if
MyGrid[[i,j]] is the directed distance from point i to point j while
MyGrid[[j,i]] is the distance in the opposite direction... but that means
there are only 10 points.
Yet you said "point A, let's say MyGrid[[10,10]]"... but that implies
there are 100 points, and you haven't told us how far from one to the
other. You're confusing the "weight" at that position in the grid with a
"point" somewhere.
Paths going up, down, left, right, or diagonal again suggests 100 points.
But what are the distances? There'd be 100*100 = 10,000 possible arcs,
less if only those directions are allowed, and many less if each "step" is
limited to one up, one down, one left, one right, or one diagonal. You
didn't say how FAR up, down, right, left, or diagonally a step might go,
or what it would cost.
Explain the problem and only THEN can anyone solve it.
Bobby
On Wed, 11 Feb 2009 04:18:34 -0600, Antonio <aneves at gmail.com> wrote:
> Dear Mathematica Users,
>
> I am not familiar with Graph theory and hope that some Mathematica
> users might help me. I am having a Shortest path problem that I hope
> to solve using Mathematica.
>
> My input is a Grid defind as,
>
> MyGrid = Table[RandomInteger[{1, 5}], {i, 1, 10}, {j, 1, 10}]
>
> in this 10x10 grid i'd like the shortest path from point A, let's say
> MyGrid[[10, 10]] to point B MyGrid[[1, 1]]. For every point inside
> this square grid I have 8 possible directions or lines
> (up,down,left,right and the 4 diagonals). The weight of each step is
> given inside the MyGrid cell, i.e. let MyGrid[[2, 3]]=1 and MyGrid[[2,
> 4]]=3
> So in going from coordinate (2,3) to (2,4) it takes 3 times as long as
> if going from (2,4) to (2,3). So all directions are possible but they
> are asymetrical in the sense that they have diferent weights if going
> foward or backward.
>
> I tried reading Mathematica help but it is very poor with no examples.
> All I know is that I have to use the Combinatorica package and the
> ShortestPath[] command, but as a start I have no idea in how to create
> a Graph needed as input to this command from MyGrid.
>
> Thanks in advanced.
>
--
DrMajorBob at longhorns.com
- References:
- Shortest Path Problem
- From: Antonio <aneves@gmail.com>
- Shortest Path Problem