Floyd-Warshall Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 10: | Line 10: | ||
* [[Johnson's Algorithm]] | * [[Johnson's Algorithm]] | ||
=Overview= | =Overview= | ||
The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative edge | The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative edge cycles. In this case there is no shortest path, because the cycle can be followed an infinite number of times, leading to negative infinity length paths. If this is the case, the Floyd-Warshall will report the situation and stop. | ||
Revision as of 23:17, 24 November 2021
External
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/VQStd/problem-definition
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/3BBkw/optimal-substructure
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/WKb60/the-floyd-warshall-algorithm
Internal
- All-Pairs Shortest Path Algorithms
- Dynamic Programming
- Bellman-Ford Shortest-Path Algorithm
- Johnson's Algorithm
Overview
The Floyd-Warshall algorithm computes all-pairs shortest path in a directed graph with arbitrary edge length, include negative lengths. The only case that does not make sense is whether the graph has negative edge cycles. In this case there is no shortest path, because the cycle can be followed an infinite number of times, leading to negative infinity length paths. If this is the case, the Floyd-Warshall will report the situation and stop.