[Boost-users] [BGL] Extending Floyd Warshall (was: All-pairs SP algorithms -> Determine the path)

On 16 April 2011 02:42, Jeremiah Willcock wrote:

Hi Jeremiah, My apology for digging up an old post. I'd like to ask how Boost's Floyd Warshall can extended to provide further functionality. I cannot find any notion of visitor for Floyd Warshall, unlike Dijkstra and A*, and I am a bit confused about the types of the arguments that have to be passed to the function.

One thing you can do in BGL is to compute the paths using the distances; look for edges where the source and target distances from a particular starting node differ by the edge's weight, and that will be in the SSSP tree for that starting node.  You can also change the distances to pairs (just by changing the types being passed into the algorithm);

Will that be a variable of type std::vector>> ? I tried this and the code failed to compile.

you would still compare just the distances, and the weight of an edge would be a pair .

Will that be a std::pair variable? Additionally, is it also possible to know the number of nodes in a shortest path between two vertices in the graph by using Boost's Floyd-Warshall implementation?

-- Jeremiah Willcock

Thank you. Best regards, Nicholas