List of all Diskstra's distance from a given source to all points in the graph

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

List of all Diskstra's distance from a given source to all points in the graph

Julien Thomas de Boer
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.


--
Sincerely,

Julien THOMAS DE BOER
Swiss Federal Institute of Technology of Lausanne (EPFL)




Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: List of all Diskstra's distance from a given source to all points in the graph

John Sichi
Administrator
Based on another email from you, I think you already figured this out,
but for the record, here's how you can do it for one start vertex:

1.  Create an instance of ClosestFirstIterator with your desired start
vertex.

2.  Call next() on it until hasNext() returns false.

3.  For each vertex reached, use the iterator's getShortestPathLength
method to get the information stored during iteration.

JGraphT doesn't currently have an all-pairs-shortest-path
implementation.  If you implement one, please consider contributing it.

http://www.cs.rochester.edu/u/leblanc/csc173/graphs/apsp.html

JVS

Julien Thomas de Boer wrote:

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


Loading...