Hi,
I have a basic implementation of the Floyd Warshall algorithm. On a
9000 node graph all pairs are calculated
in ~ 36h using a 4Ghz / 4Gb memoerySun cluster. You are welcome to it
but it is entirely independent of jgrapht,
I am only an infrequent jgrapht user so would need some help in
converting it. You are welcome to it as is.
The algorithm stores distances in a byte [][] - so e.g., a 9000 node
graph needs an 81Mb array.
It is much faster than running DjisktraSP repeatedly - I have access to
a parallel computing cluster and even running
DSP on 8 threads is not faster than FW.
Regards
Richard
jgr...@li... wrote:
>Send jgrapht-users mailing list submissions to
> jgr...@li...
>
>To subscribe or unsubscribe via the World Wide Web, visit
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>or, via email, send a message with subject or body 'help' to
> jgr...@li...
>
>You can reach the person managing the list at
> jgr...@li...
>
>When replying, please edit your Subject line so it is more specific
>than "Re: Contents of jgrapht-users digest..."
>
>
>Today's Topics:
>
> 1. List of all Diskstra's distance from a given source to all points
> in the graph (Julien Thomas de Boer)
> 2. Re: List of all Diskstra's distance from a given
> source to all points in the graph (John V. Sichi)
>
>--__--__--
>
>Message: 1
>From: Julien Thomas de Boer <jul...@ep...>
>To: jgr...@li...
>Date: Tue, 02 Aug 2005 13:40:33 +0200
>Subject: [jgrapht-users] List of all Diskstra's distance from a given source to all points
> in the graph
>
>Hi everyone,
>I want to compute the mean distance in a Jgrapht graph. So, I have to
>compute distances for each possible pairs in the graph. But computing
>Dijsktra for each pairs is taking too much time. I heard that
>Dijkstra didnt give you only the shortest path between the source node
>and the target node but also between the source and all nodes in the
>graph at the same time. is it the case in the current implementation of
>dijkstra in Jgraht? If yes, how can I retrieve this list of distances.
>Thanks for your help.
>
>
>
>
--
Dr Richard Adams
Psychiatric Genetics Group,
Medical Genetics,
Molecular Medicine Centre,
Western General Hospital,
Crewe Rd West,
Edinburgh UK
EH4 2XU
Tel: 44 131 651 1084
ric...@ed...
|
