[Boost-users] BGL - shortest widest path

Subject: [Boost-users] BGL - shortest widest path
From: Mark Fanara (mfanara_at_[hidden])
Date: 2014-11-12 17:34:35

I am trying to find the "shortest-widest path" between a single source and target node in an undirected graph (less than 25 nodes). (In my case, a shortest widest path is the maximum bandwidth path. If there are several such paths, it is the one with the least number of hops.)  See W i k i p e d i a entry on "Widest path problem"

I have successfully used dijkstra_shortest_paths() with a custom combine() function to find the maximum bandwidth path, however this does not take into account the possibility of more than one path with the same maximum bandwidth. In that case, I am looking for the one with the fewest hops.

I am not clear on the meaning of some of the graph theory terms --- Is the problem I am trying to solve similar too, or the same as, a maximum flow problem? If so, as I am using an undirected graph, which boost algorithm should I use and how should I create a directed graph from my undirected graph?

Would really appreciate an example, perhaps something that prints the resulting vertices in from-source-to-sink order.