On 13/01/2016 13:40, alex wrote:
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've gone with (2) for now, and this appears to be working absolutely
fine. It's certainly giving the same results as the manually computed
tables currently in use, which is good!
One thing I'm not totally sure about is how to get an edge list from
dijkstra_shortest_paths.
Graph g; // pre-filled
vertex_descriptor start // set elsewhere
std::vector