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

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-12-07 09:38:28

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'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).

Interesting.

We're always interested in growing the BGL with new and interesting  
algorithms. When you think your implementation is ready to go into  
Boost, please send it to the list or to me privately. We usually go  
through a quick round of review (or two) to make sure it fits well  
with the BGL style, then it'll go in the next release.

I'm looking forward to seeing this algortihm!

        Cheers,
        Doug