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