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.