Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2009

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

Search the Archive

Re: Shortest Path Problem

  • To: mathgroup at smc.vnet.net
  • Subject: [mg96395] Re: Shortest Path Problem
  • From: dh <dh at metrohm.com>
  • Date: Thu, 12 Feb 2009 06:43:29 -0500 (EST)
  • References: <gmu8kl$ggb$1@smc.vnet.net>


Hi Antonio,

assume we have a weight matrix w. From w we create a graph: g. We then 

serach the shortest path from vertex 1 to 4. Finally we display the 

costs of all shortest paths:

w = {{3, 7, 2, 6}, {7, 9, 3, 1}, {3, 2, 7, 6}, {9, 3, 6, 10}};

g = FromAdjacencyMatrix[w, EdgeWeight, Type -> Directed];

ShortestPath[g, 1, 4 ]

AllPairsShortestPath[g]



hope this helps, Daniel





ntonio 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: Shortest Path Problem
  • Next by Date: Re: Reposted, Reformatted Re: "mapping" functions over lists, again!
  • Previous by thread: Re: Shortest Path Problem
  • Next by thread: Re: Shortest Path Problem