MathGroup Archive 2009

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

Search the Archive

Re: Shortest Path Problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg96500] Re: Shortest Path Problem
  • From: DeLouis Dana <dana.del at gmail.com>
  • Date: Sat, 14 Feb 2009 04:15:06 -0500 (EST)

 > (up,down,left,right and the 4 diagonals)

 > So all directions are possible but they
 > are asymetrical in the sense that they have diferent weights if going
 > foward or backward.
 > All I know is that I have to use the Combinatorica package

Hi.  Here are some commands you may find helpful.
This is not complete because the diagonals are not complete.
I'm not sure what an efficient method for the diagonals would be just  
yet.
I'm using Mathematica ver 7.

Because the diagonals are not complete, I made it a simple graph by  
removing the double path (combined path 2-3, and 3-2)

This is just a 5 * 5 grid.
Hopefully, this will give you some ideas to work with.

Needs["Combinatorica`"]

n = 5;
g = GridGraph[n, n];
g = SetEdgeWeights[g, RandomInteger[{1, 5}, M[g]]];

diag = Table[
    s = (r - 1)*n + c;
    {{s, s + n + 1}, {s, s + n - 1}, {s, s - n + 1}, {s,
      s - n - 1}}, {r, 2, n - 1}, {c, 2, n - 1}];

diag = Flatten[diag, 2] // Sort;

g = AddEdges[g, diag];

g = SetEdgeWeights[g, diag, RandomInteger[{1, 5}, Length[diag]]];

  g = MakeSimple[g];

pth = Partition[ShortestPath[g, 1, n*n], 2, 1];

g = SetEdgeLabels[g, GetEdgeWeights[g]];

ShowGraph[
  Highlight[g, {pth},
   HighlightedEdgeColors -> Red],
  VertexNumber -> True,
  VertexNumberColor -> Blue]

= = =
HTH
Dana DeLouis


Antonio 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: Problem with DSolve
  • Next by Date: Re: Chain Matrix
  • Previous by thread: Re: Shortest Path Problem
  • Next by thread: Re: Shortest Path Problem