Which dynamic programming algorithm is used to find all-pairs shortest paths in a weighted graph in O(V³) time?
Show answer
Floyd-Warshall algorithm
The Floyd-Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is distinct for its simplicity and its ability to handle negative edge weights, provided there are no negative cycles.
Also asked as:
- Which O(V³) dynamic programming algorithm calculates the shortest paths between all pairs of vertices in a weighted graph?