
Boost Users : 
Subject: [Boostusers] BGL  shortest widest path
From: Mark Fanara (mfanara_at_[hidden])
Date: 20141112 17:34:35
I am trying to find the "shortestwidest 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 fromsourcetosink order.
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