[Boost-users] [BGL] Shortest-Path subject to length constraint

Subject: [Boost-users] [BGL] Shortest-Path subject to length constraint
From: Yun Liu (yunliu_at_[hidden])
Date: 2014-11-13 09:48:27

Hi all, apologies in advance if this question is trivial; I couldn't 
find anything like it asked previously in the mailing list.

My question is, if I have a directed graph (with non-negative edge 
weights, to keep things simple for now), I would like to find the 
shortest-cost path from a source node to target node, but with the 
constraint on the maximum number of edges allowed.

For example, if I have the graph with vertices {A,B,C,D} and edges:
A->B (cost 1),
B->C (cost 1),
C->D (cost 1),
A->D (cost 1000),

but I have the constraint that my path should only be a maximum of 2 
edges, the correct solution would still be A->D with cost 1000.

Looking through the previous BGL examples, say with bellman-ford or 
Dijkstra, it did not seem immediately obvious how to enforce this 
stipulation.

Thanks again for any ideas!

-Yun