Geek asks and answers

Floyd Warsall remodels the path

I want to restore the path from the top of the source to the address in this graph problem.

How can I save the path and how to get it after I find the minimum cost from s to d?

Please help me find a simple answer?

For example, at the point

adjmat[i][j] = Math.min(adjMat[i][j],adjMat[i][k]+adjMat[k][j]);

I need to add a path, and I need to restore it.

+3
source share
2 answers

The Wikipedia article on the Floyd-Warsall algorithm contains a description and pseudocode for your problem.

+3
source

Use the optimal matrix with the Floyd-Warsall algorithm to reconstruct the path. He constructs a path of imitation. See Introduction to Graph Theory - Narsing Deo for a Real Algorithm

+1
source

More articles:


All Articles