MathGroup Archive 2009

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

Search the Archive

Re: Shortest Path Problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg96381] Re: Shortest Path Problem
  • From: "Sjoerd C. de Vries" <sjoerd.c.devries at gmail.com>
  • Date: Thu, 12 Feb 2009 06:40:53 -0500 (EST)
  • References: <gmu8kl$ggb$1@smc.vnet.net>

Dear Antonio,

Here's a complete example. Hope this helps.

Cheers -- Sjoerd

Needs["Combinatorica`"]

MyGrid = Table[RandomInteger[{1, 5}], {i, 1, 10}, {j, 1, 10}];

sp = ShortestPath[
   FromAdjacencyMatrix[
    Partition[
     Apply[
      If[ChessboardDistance[#1, #2] == 1, (*allow adjacent fields
only*)
        MyGrid[[#2[[1]], #2[[2]]]], \[Infinity]] &, (*weight
determined by goal field*)
      Tuples[Flatten[Table[{i, j}, {i, 10}, {j, 10}], 1], 2], (*for
all checkerboard field combinations, i.e. 100x100 combinations *)
      {1}
      ], 100 (* make a matrix  instead of a list*)
     ], EdgeWeight
    ],
   1, 100 (*start, end*)
   ];

MatrixPlot[MyGrid,
 Epilog ->
  Line[{Mod[sp, 10, 1] - 0.5,
     Quotient[sp - Mod[sp, 10, 1], 10] + 0.5}\[Transpose]], (* map
field numbers to coordinates *)
 DataReversed -> True]


On Feb 11, 12:17 pm, Antonio <ane... 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.



  • Prev by Date: Re: Help! About drawing a high-precision 3D graph
  • Next by Date: Re: Shortest Path Problem
  • Previous by thread: Re: Shortest Path Problem
  • Next by thread: Re: Shortest Path Problem