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

Subject: Re: [Boost-users] [BGL] k-shortest path
From: Vicky Vergara (vicky_vergara_at_[hidden])
Date: 2015-10-20 12:02:31

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_at_[hidden]
> To: boost-users_at_[hidden]
> 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
> > <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
> >
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users