Re: [Boost-users] All-pairs SP algorithms -> Determine the path

On Fri, 15 Apr 2011, Nicholas Mario Wardhana wrote:

On 15 April 2011 22:25, GOO Creations wrote:

...

Hi again

I've noticed that the all-pairs SP algorithms (eg: Johnson, Floyd-Marshall) only "return" a distance matrix that hold the shortest distances between any node n and n'. Is there a way to determine the actual path (eg: n2-n4-n5-n1-n0) between these nodes using the all-pairs algorithms?

Chris

Hi Chris,

As the names suggest, AFAIK those algorithms definitely only compute the lengths of the shortest paths between all pairs of nodes (please CMIIW). If you want to determine the actual path, there is one article written by Ian Millington mentioning a modified Floyd-Warshall (not Marshall!) algorithm that can do it. You can find it here:

http://idm.me.uk/ai/wfi.pdf .

However, I am not sure whether the implementation in Boost can do this, and neither do I know how it can be modified to compute the path. Anyway, I think the algorithm is quite simple and can be easily implemented.

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); you would still compare just the distances, and the weight of an edge would be a pair . -- Jeremiah Willcock