Boost logo

Boost Users :

Subject: [Boost-users] [graph] Search algorithm using quality metric rather than distance
From: rleigh_at_[hidden]
Date: 2016-01-13 06:53:38

I have an adjacency_list graph (shown in attached dot file). Each edge has
an attached "quality metric" as a bundled property.

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'll likely then look at the number of edges and then select the shortest
of the candidates.

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,

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at