
Boost Users : 
Subject: Re: [Boostusers] [graph] Search algorithm using quality metric rather than distance
From: alex (alexhighviz_at_[hidden])
Date: 20160113 08:40:19
>From: rleigh_at_[hidden]
>Sent: 13 January 2016 11:54
>Similar to the dijkstra_shortest_paths algorithm, I'd like to determine
>the optimal path. However, this algorithm sums the distance along each
>edge, and finds the shortest path. What I'd like to do is *multiply* the
>quality metric for each edge in the path, and find the largest one. A
>perfect path will have a quality metric of 1.0, while suboptimal paths
>will have values tending towards zero, and the more "bad" edges the
>smaller the number.
>
I think you can use dijkstra_shortest_paths and have two options to do so:
1 .You can provide the Dijkstra algorithm with the appropriate
CombineFunction, CompareFunction, DistZero and DistInf (CombineFunction =
std::multiplies, CompareFunction = std::greater, DistZero = 1, DistInf =
0;)
2. You can logtransform the quality metrics, using w = log(q), where w is
the transformed weight for the WeightMap
>I'll likely then look at the number of edges and then select the shortest
>of the candidates.
Dijkstra will not give you multiple candidates, but just one highestquality
path.
If you want a more complex distance that considers both the number of edges
in path and their quality, you might be best of with a
std::tuple<QualityType, EdgeCountType> for Distance and provide the Dijkstra
algorithm with the appropriate CombineFunction, CompareFunction, DistZero
and DistInf.
>
>It seems like a simple algorithm that might already be included, but I
>just haven't found it yet not knowing its formal name. If anyone has any
>suggestions, I'd be very grateful.
>
>
>Many thanks,
>Roger
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net