Explain the Floyd-Warshall Algorithm.

Explain the Floyd-Warshall Algorithm.

Approach: Describe an all-pairs shortest path algorithm.

A dynamic programming algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It compares all possible paths through the graph between each pair of vertices.

Follow-up: How do you detect a negative cycle using this algorithm?

Key concepts: adjacency matrix, O(V^3), dynamic programming.