A powerful algorithm to compute all-pairs shortest path.
The Math background of this problem is related to Relations. Specifically, it is related to transitive closure problem. Floyd-Warshall algorithm can be used to compute the transitive closure of a graph efficiently (O(n^3)).
In addition, Floyd-Warshall algorithm is very easy to implement.
No comments:
Post a Comment