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

Subject: Re: [Boost-users] All-pairs SP algorithms -> Determine the path
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-04-15 14:42:50

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

> On 15 April 2011 22:25, GOO Creations <goocreations_at_[hidden]> 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 
<distance, predecessor> 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 <actual_weight, source>.

-- Jeremiah Willcock