Shortest Path Problem
- To: mathgroup at smc.vnet.net
- Subject: [mg96293] Shortest Path Problem
- From: Antonio <aneves at gmail.com>
- Date: Wed, 11 Feb 2009 05:18:34 -0500 (EST)
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.
- Follow-Ups:
- Re: Shortest Path Problem
- From: Daniel Lichtblau <danl@wolfram.com>
- Re: Shortest Path Problem
- From: DrMajorBob <btreat1@austin.rr.com>
- Re: Shortest Path Problem