On Tue, Apr 8, 2014 5:38 AM PDT Sensei wrote:
Dear all,
after many speculations and your previous advice I've come to the conclusion that I still need your help :)
The setting is simple: I have an oriented graph, and I have two nodes. I wish to find all paths from one node to the other.
Some restrictions apply: - I *cannot* calculate weights except at run-time when needed, it's too costly; - I can, if you say it's needed, restrict the path length to a certain threshold.
What can I relax? The "all paths". Since weights are costly, I could set for just the best path, i.e., the one with the lowest weight. I don't think it would be possible to find the optimum path, in case I cannot search for all possible paths, but I can be easily wrong.
I'm not that skilled with BGL, so any help would be quite appreciated! I've read the Table of Contents, but at first I cannot see if this can be done.
You might consider using A* search instead of a normal shortest path algorithm. You don't need a heuristic function (just use one that always returns zero). There is a function_property_map type that you can use to turn a weight-computing function into a property map. -- Jeremiah Willcock