Re: [boost] [graph] Proposal: Algorithm for the Shortest Path Problem with Resource Constraints

From: Oliver Kullmann (O.Kullmann_at_[hidden])
Date: 2005-12-07 11:31:41

On Wed, Dec 07, 2005 at 09:38:28AM -0500, Douglas Gregor wrote:
> 
> On Dec 6, 2005, at 1:59 PM, Michael Drexl wrote:
> > is there any interest in including an algorithm for solving the  
> > shortest
> > path problem with resource constraints (SPPRC) in the Boost Graph  
> > library?
> 
> Yes!
>

I would second it; many more algorithms are needed.
 
> > I've implemented an exact algorithm for this NP-hard problem. The
> > algorithm is basically a label-setting algorithm based on dynamic
> > programming. It is parameterized on the graph type (of course) and the
> > type of the resource container (data structures specifying what
> > resources there are and how they are to be managed in the course of  
> > the
> > algorithm).

For such hard problems there is an enormous design space (and an even
bigger algorithm space) to be considered, so a good dose of genericity
in the implementation would be appreciated (hopefully it comes with
concepts?).

Since it's NP-hard, it would be good to have also a reduction from
some well-known NP-complete problem to SPPRC (for example graph
colouring), which would be very useful for testing (using some
established implementation for that NP-complete problem).

Oliver