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-11-22 03:11:58

Hi Jeremy and others,

I implemented the edge-disjoint KSP, but without a min-cost max-flow 
algorithm.  You can find the implementation here:

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

Jeremy, did you try to implement Yen?  I think I'll have a stab at it.

Best,
Irek

On 12.10.2015 14:35, Ireneusz Szcześniak wrote:
> 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
>>
>