Advanced Topic 36 of 51 Algorithms
Floyd-Warshall Algorithm
All-pairs shortest paths via dynamic programming.
How it works
A DP over intermediate vertices: d[i][j] = min(d[i][j], d[i][k] + d[k][j]) for each k, computing all-pairs shortest paths in O(V³).
Where it is used
Small dense graphs, transitive closure.
Common pitfall
Cubic time is expensive; order of the k loop must be outermost.
Where it fits in the course
Floyd-Warshall Algorithm is topic 36 of 51 in Algorithms, rated Advanced. It follows Bellman-Ford Algorithm. The next topic is A* Search.
Practice and explore
- Open the interactive lesson, with a mini quiz.
- Take the Algorithms quiz.
- Explore the Graph Traversal visualizer: BFS, DFS and Dijkstra on a weighted graph.
How to study this topic
- Read the explanation above and restate the definition in your own words.
- Open the interactive lesson and answer its mini quiz.
- Read the common pitfall, then write a short example that avoids it.
- Check your understanding in the Algorithms quiz, and revisit the topic if you miss a question.
Frequently asked questions
What is Floyd-Warshall Algorithm?
All-pairs shortest paths via dynamic programming. It belongs to Algorithms and is an advanced-level topic.
Where do people use Floyd-Warshall Algorithm?
Small dense graphs, transitive closure.
What is the most common mistake with Floyd-Warshall Algorithm?
Cubic time is expensive; order of the k loop must be outermost.
What should I learn before this topic?
Start with Bellman-Ford Algorithm, the topic just before it in Algorithms.
How can I practice it?
Answer the mini quiz in the interactive lesson, then take the Algorithms quiz. You can also explore Graph Traversal in the Visual Lab.
Is Floyd-Warshall Algorithm hard to learn?
It is an Advanced topic. Expect to read the explanation more than once and to connect it with earlier topics. Working through a small example by hand helps most.
How long does it take to learn Floyd-Warshall Algorithm?
Most learners can read the explanation and finish the interactive lesson in under an hour. Fluency comes from applying the idea, so plan a few short practice sessions with the quiz.
Which topics are related to Floyd-Warshall Algorithm?
Bellman-Ford Algorithm, A* Search, Dijkstra's Algorithm are closely connected. The full list is in the related topics section of this page.
What should I study after Floyd-Warshall Algorithm?
Continue with A* Search, the next topic in Algorithms.
Related topics
- Bellman-Ford Algorithm (Algorithms)
- A* Search (Algorithms)
- Dijkstra's Algorithm (Algorithms)
- Minimum Spanning Tree (Algorithms)
- Shor's Algorithm (Emerging & Frontier Topics)
- Grover's Algorithm (Emerging & Frontier Topics)