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

Subject: Re: [Boost-users] All-pairs SP algorithms -> Determine the path
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 2011-04-15 10:41:31

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.

Best regards,
Nicholas