Re: [Boost-users] [Graph] Run-time weight search

Subject: Re: [Boost-users] [Graph] Run-time weight search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2014-04-10 02:10:13

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