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-02-01 11:01:12
|
ok, just downloaded the 703 revision from the svn, as i read about some optimizations in the floyd warshall code... I tried Floyd-Warshall with a 1000 vertex / 2000 edges graph and it completed in less than 2 minutes on the same machine as above. Using repeated(n^2) Dijkstra invocations, my overall time complexity was O(n^4) and now is O(n^3), which is more acceptable. I will try with increasingly bigger graph sizes and keep you informed. Alessandro 2010/1/29 andrea pagani <pag...@gm...> > Hi Alessandro, > > I'm using FloydWarshall on samples about 200 nodes and it works pretty > well, but you have a far bigger sample. > Give it a try. > Let me know if it's fast even with this big sample. > > Thanks, > > Andrea > > On Fri, Jan 29, 2010 at 6:37 PM, Alessandro Marco Boutari < > a.m...@gm...> wrote: > >> 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 >> > >> >> >> ------------------------------------------------------------------------------ >> >> 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 >> > > |
