Re: [jgrapht-users] KShortestPaths performance

[Charles G. <cg...@lh...>]

Hi Ernst

Good question :)  I am currently using postgresql/postgis/pgrouting and it's Dijkstra routing algorithm for my routing and it works well for a single shortest route from one point to another.  A single route is usually a few hundred milliseconds.  However I now need to generate the n shortest routes between two points so they can be offered as alternatives, where depending on the results I expect to to be anywhere from 3 to 10 (I am unsure the differences in routes will all be useful) and I'd like to keep this under a second as well.

I don't think I need the negative weight as it is a fully directed graph so each vertex is one-way. Is there a way I can make this faster without that?

This morning I'll try the other algorithms as a comparison to pgrouting, as well as try build a smaller graph each time I do the routing and see what that does for the speed as well.

Thanks,
charles

On Sep 12, 2011, at 3:26 AM, hnr...@gr... wrote:

> Dear Charles,
> 
> What ARE your needs?
> 
> Depending on what they are, I dare say they can be fulfilled faster than the KShortestPaths algorithm does, because
> 1. This algorithm can handle negative weight cycles. Do you need this?
> 2. Your graph is very sparse.
> 
> Did you try e.g. the Dijkstra or Floyd-Warshall algorithms?
> 
> Regards,
>   Ernst