
Boost Users : 
Subject: Re: [Boostusers] Allpairs SP algorithms > Determine the path
From: Nicholas Mario Wardhana (mario.wardhana_at_[hidden])
Date: 20110415 10:41:31
On 15 April 2011 22:25, GOO Creations <goocreations_at_[hidden]> wrote:
> Hi again
>
> I've noticed that the allpairs SP algorithms (eg: Johnson, FloydMarshall)
> 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:
> n2n4n5n1n0) between these nodes using the allpairs 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 FloydWarshall (not
Marshall!) algorithm that can do it. You can find it here:
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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net