Re: Shortest path algorithm
- To: mathgroup at smc.vnet.net
- Subject: [mg45308] Re: [mg45302] Shortest path algorithm
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Tue, 30 Dec 2003 04:14:16 -0500 (EST)
- References: <200312290522.AAA14975@smc.vnet.net> <B3699266-39F6-11D8-A71B-00039311C1CC@mimuw.edu.pl>
- Sender: owner-wri-mathgroup at wolfram.com
I have to make a correction. AllPairsShortestPath uses the
Floyd-Warshall algorithm, not the Dijkstra algorithm.
Andrzej Kozlowski
On 29 Dec 2003, at 21:01, Andrzej Kozlowski wrote:
> 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