Floyd–Warshall Algorithm

When to Use Floyd-Warshall

• Dense graphs with up to a few hundred vertices
• All-pairs distance queries are required
• Graphs containing negative edge weights
• Computing transitive closure of a graph

Core Idea

The algorithm incrementally improves path estimates between every pair of vertices. For each intermediate vertex 'k', it checks if passing through 'k' provides a shorter path than the current known distance between i and j.