Re: [jgrapht-users] Shortest path, alternatives?
Brought to you by:
barak_naveh,
perfecthash
Menu
▾
▴
Re: [jgrapht-users] Shortest path, alternatives?
|
From: Alessandro M. B. <a.m...@gm...> - 2010-01-29 17:38:10
|
hey it's exactly what i need! I wasn't aware of the existence of this algorithm! Thank you very much, I'll try it asap. Alessandro Il 29/01/2010 18.30, John V. Sichi ha scritto: > 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 > |
