[jgrapht-users] Shortest path, alternatives?

[Alessandro M. B. <a.m...@gm...>]

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