Graphs
Shortest Path Algorithms
Count: 10
Pre-Requisite: Depth-First Search, Breadth-First Search
Finding shortest paths is one of the most fundamental graph problems. The algorithm you choose depends on one thing: what are the edge weights?
Shortest path algorithm decision tree
Let's have a look on each algorithm below.
1. BFS: When All Edges Are Equal
If every edge has the same cost (or weight = 1), BFS is your shortest path algorithm. If you're unfamiliar with BFS, start with our BFS introduction.
How BFS Finds Shortest Paths
BFS explores nodes level by level using a queue. The first time you reach a node, you've found the shortest path to it and no other path can be shorter because all edges cost the same.
Walkthrough
Complexity
When to Use BFS
Problems That Use BFS for Shortest Path
2. Dijkstra's Algorithm: Non-Negative Weights
How Dijkstra Works
Walkthrough
Why It Works
Complexity
When to Use Dijkstra
Classic Dijkstra Problems
3. Bellman-Ford: When Negative Weights Exist
How Bellman-Ford Works
Why V-1 Iterations?
Walkthrough
Complexity
When to Use Bellman-Ford
4. Floyd-Warshall: All Pairs Shortest Path
How Floyd-Warshall Works
Walkthrough
Complexity
When to Use Floyd-Warshall
Classic Floyd-Warshall Problem
Quick Reference
Algorithm Selection
Complexity Comparison
Key Takeaways
Practice Problems
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium