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