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

Subject: [Boost-users] [BGL] Extending Floyd Warshall (was: All-pairs SP algorithms -> Determine the path)
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2011-04-27 01:01:24

On 16 April 2011 02:42, Jeremiah Willcock <jewillco_at_[hidden]> 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 <distance,
> predecessor> pairs (just by changing the types being passed into the
> algorithm);

Will that be a variable of type
std::vector<std::vector<std::pair<float, boost::vertex_descriptor>>> ?
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 <actual_weight, source>.

Will that be a std::pair<float, vertex_descriptor> 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