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

Subject: Re: [Boost-users] [BGL] k-shortest path
From: Ireneusz Szcześniak (irek.szczesniak_at_[hidden])
Date: 2015-12-11 02:35:19

Hi Jeremy and others,

FYI, I implemented the Yen algorithm:

https://svn.boost.org/trac/boost/ticket/11838

Best,
Irek

On 11.10.2015 08:36, Jeremy Murphy wrote:
> Hi Irek,
>
> On 8 October 2015 at 23:43, Ireneusz Szcześniak
> <irek.szczesniak_at_[hidden] <mailto: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
>
>
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>