[jgrapht-users] Re: APSP problem.

[Richard A. <Ric...@ed...>]

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