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

Subject: Re: [Boost-users] [BGL] k-shortest path
From: Jeremy Murphy (jeremy.william.murphy_at_[hidden])
Date: 2015-10-11 02:36:34

Hi Irek,

On 8 October 2015 at 23:43, Ireneusz Szcześniak <irek.szczesniak_at_[hidden]>
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