[BGL] Shortest-Path subject to length constraint
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
participants (1)
-
Yun Liu