Re: Shortest path algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg45307] Re: [mg45302] Shortest path algorithm
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 30 Dec 2003 04:14:15 -0500 (EST)
- References: <200312290522.AAA14975@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
On 29 Dec 2003, at 14:22, gio wrote:
> Dear all,
>
> Currently I am working on a subproject for my PhD. In this subproject I
> need to do some analysis on a network.
>
> I have about 1000 vertices. Every vertex is connected to about 20
> (definately not more) vertices.
>
> I need to know what the shortest path is from every vertex to all other
> vertices in the network. Total distance/weight is not that relevant to
> show up.
>
> Are there any Mathematica algorithms out there that can deal with this
> stuff? Or can anybody help me by telling me how to tackle this problem?
>
> Best regards,
>
> Ralph
>
> ralphmic(at)inter(dot)nl(dot)net
> replace (at) by @
> replace (dot) by .
>
>
The Combinatorica package has the function AllpairsShortestPath that
ought to do what you want. I'll first demonstrate how to use it on a
small graph.
This loads the Combinatorica package:
<< "DiscreteMath`Combinatorica`"
This defines a random graph with 10 vertices and the probability f an
edge between any two vertices 0.4. The weights are integers selected at
random form the range 1 to 1000.
gr = SetEdgeWeights[RandomGraph[10, 0.4],
WeightingFunction -> RandomInteger,
WeightRange -> {1, 1000}]
Out[6]=
"â??Graph:<"*15*", "*10*", "*"Undirected"*">â??"
One can use either the Dijkstra or the BellmanFord algorithm. However,
at the moment I am not convinced that the latter is correctly
implemented. In any case, Dijkstra should be more efficient for your
problem. This tells you the sortest distances form the first vertex to
all other vertices.
Last[Dijkstra[gr, 1]]
Out[7]=
{0, 306, 503, 740, 812, 275, 701, 567, 525, 677}
And this makes a table of shortest distances between any pairs of
vertices. (You should use TableForm to get a more readable output).
In[12]:=
AllPairsShortestPath[gr]
Out[12]=
{{0, 306, 503, 740, 812, 275, 701, 567, 525, 677},
{306, 0, 746, 434, 506, 31, 395, 261, 219, 371},
{503, 746, 0, 1180, 1252, 777, 399, 1007, 965,
375}, {740, 434, 1180, 0, 561, 465, 829, 695,
653, 805}, {812, 506, 1252, 561, 0, 537, 901,
245, 287, 877}, {275, 31, 777, 465, 537, 0,
426, 292, 250, 402}, {701, 395, 399, 829, 901,
426, 0, 656, 614, 24}, {567, 261, 1007, 695,
245, 292, 656, 0, 42, 632},
{525, 219, 965, 653, 287, 250, 614, 42, 0, 590},
{677, 371, 375, 805, 877, 402, 24, 632, 590, 0}}
So now the question is: will this be enough for your problem? Of course
this depends on the speed of your computer and the size of your memory
and how long you are willing to wait. I do not wish to try it on a
problem your size but I will choose a graph approximately 10 times
smaller:
This time the graph has 100 vertices, with the probability of an edge
equal to 0.02.
gr=SetEdgeWeights[RandomGraph[100,0.02],WeightingFunction-
>RandomInteger,
WeightRange->{1,1000}]
â??Graph:< 120 , 100 , Undirected >â??
The average number of edges is:
N[Mean[DegreeSequence[gr]]]
2.4
Timing[AllPairsShortestPath[gr];]
{3.96 Second,Null}
This took approximately 4 seconds on my 400 mghz computer. When I tried
it one a graph with 200 vertices I it about 40 seconds. Since the
running time of the algorithm is O(n^3), so I would expect running your
problem on my computer to take over an hour.
Andrzej Kozlowski
- References:
- Shortest path algorithm
- From: gio <gio@nospam.com>
- Shortest path algorithm