From: rleigh@codelibre.net 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 log-transform 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 highest-quality 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