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