Re: [Boost-users] [BGL] k-shortest path

You can find an implementation of Yen Algorithm using Boost.Graph in pgRouting http://pgrouting.org/ In version 2.1 which is the latest release, can be found here: https://github.com/pgRouting/pgrouting/releases/tag/pgrouting-2.1.0

Date: Mon, 12 Oct 2015 14:35:52 +0200 From: irek.szczesniak@gmail.com To: boost-users@lists.boost.org Subject: Re: [Boost-users] [BGL] k-shortest path

Hi Jeremy,

Thanks for your email. No, I haven't tried implementing Yen or Eppstein in BGL. I was hoping to use something that already exist.

I guess I'll just go for edge-disjoint shortest paths with the min-cost max-flow algorithm already present in Boost, i.e.:

successive_shortest_path_nonnegative_weights

Best, Irek

On 11.10.2015 08:36, Jeremy Murphy wrote:

...

Hi Irek,

On 8 October 2015 at 23:43, Ireneusz Szcześniak mailto:irek.szczesniak@gmail.com> wrote:

I need to find k-shortest paths, but there is no such algorithm in BGL. I can get edge-disjoint k-shortest paths with a max-flow algorithm, but I don't need the k-shortest path to be edge-disjoint -- that's too strict for me.

I would appreciate it if someone could share an implementation of the Yen or Eppstein algorithms using BGL. I found some implementations on the Internet, but they don't use BGL.

As you may already know, Eppstein and Yen algorithms are different with respect to loops, so be sure which one you need.

You may also wish to consider K*: http://www.sciencedirect.com/science/article/pii/S0004370211000865

You don't have to be a BGL guru to implement algorithms that work on BGL graphs: have you tried giving it a go? Admittedly, you have piqued my curiosity and now I will probably have a go.

Cheers.

Jeremy

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users