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>