MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Shortest Path Problem

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,
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.

  • Prev by Date: simplifying RotationMatrix
  • Next by Date: Re: Manipulating list of functions
  • Previous by thread: Re: simplifying RotationMatrix
  • Next by thread: Re: Shortest Path Problem