Re: [jgrapht-users] Shortest path, alternatives?

[John V. S. <js...@gm...>]

Have you tried the FloydWarshallShortestPaths implementation in JGraphT?

JVS

Alessandro Marco Boutari wrote:
> Hello everybody,
> 
> I am using the JgraphT library in a project related to document 
> indexing. At some point I need to find the shortest path between all the 
> possible vertex pairs, and this is a serious bottleneck: given a graph 
> with 800 vertex and 2000 edges, it takes about 30 minutes on a Mac dual 
> core (already taken into account some multithreading and calculating 
> only half the distance matrix) to complete the full calculation and this 
> is only a test graph, the useful ones are much bigger than that.
> 
> So I would like to know:
> 
> 1) can you confirm the actual implementation of dijkstra shortest path 
> has a complexity of O(n^2)?
> 2) I had a look at the code and it seems that it calculates for each 
> node a spanning tree. Could it be possible to modify the code to make it 
> return a one-to-all shortest path calculation?
> 3) are there any better alternatives to dijkstra algorithm/implementation?
> 4) if answer to 3) is yes, would they be compatible with the graph 
> representation used in JgraphT?
> 
> thank you in advance
> Alessandro
> 
> 
> ------------------------------------------------------------------------
> 
> ------------------------------------------------------------------------------
> The Planet: dedicated and managed hosting, cloud storage, colocation
> Stay online with enterprise data centers and the best network in the business
> Choose flexible plans and management services without long-term contracts
> Personal 24x7 support from experience hosting pros just a phone call away.
> http://p.sf.net/sfu/theplanet-com
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users