On 15 April 2011 22:25, GOO Creations
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