Warshall / Floyd / Ingerman Algorithm (for finding shortest paths)
The graph can include negative weights.
This algorithm also allows us to detect cycles if the diagonal is initialized to inf and not to zero. If any of the diagonal values are changed, then the graph contains a cycle. Basically, if the cost / distance from node A to node A is not inf, it contains a cycle.
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
The graph can include negative weights.
This algorithm also allows us to detect cycles if the diagonal is initialized to inf and not to zero. If any of the diagonal values are changed, then the graph contains a cycle. Basically, if the cost / distance from node A to node A is not inf, it contains a cycle.
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
No comments:
Post a Comment