Shortest Path Algorithms, when to Use What?

* Graphs are maps. * Edges are roads. * Weights are cost, time, or distance. Shortest path algorithms answer one question: > What is the cheapest way to go from here to there? But there is no single algorithm for all situations. Choosing the right one is the real skill. This guide covers: 1. BFS 2. Dijkstra 3. Bellman–Ford 4. Floyd–Warshall * **When to use each** * **Time & Space complexity** * **Real LeetCode problems** * **Simple memory tricks** --- ## 1. BFS (Breadth First Search) **Use when:** All edges have equal weight (or weight = 1). Example scenarios: * Minimum steps in a grid * Shortest moves in a game * Unweighted graph **Core Idea** *Explore level by level.* ``` Start → neighbors → neighbors of neighbors ``` Each level = distance +1 **Time Complexity:** `O(V + E)` **Space Complexity:** `O(V)` * [Word Ladder]("https://leetcode.com/problems/word-ladder/") * [ Rotting Oranges](https://leetcode.com/problems/rotting-oranges/) * [Nearest Exit in Maze](https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/) **Memory Trick** > Same cost roads → Use a queue → BFS ## 2. Dijkstra’s Algorithm **Use when:** * Weighted graph * All weights are **non-negative** * Need shortest path from **one source** * Greedy in nature * Practically used in **Navigation**, **Link State Routing** This is the most common shortest path algorithm in interviews. It always expands the node with the smallest current distance using a **min-heap**. **Time Complexity:** `O((V + E) log V)` > You process each node once and each edge once, and every time you update or pick the smallest distance it costs log V (heap work), so total time is O((V + E) log V) — basically “touch everything, and each touch pays a log-tax.” **Space Complexity:** `O(V + E)` **LeetCode** * [Network Delay Time](https://leetcode.com/problems/network-delay-time/) * [Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) * [Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/) **Memory Trick** > Different positive costs → Use a min-heap → Dijkstra ## 3. Bellman–Ford **Use when:** * Graph may contain **negative weights** * Need to detect **negative cycles** * Practically used in **Distance Vector Routing(DVR)** Dijkstra fails if negative edges exist. Bellman–Ford handles them by relaxing all edges repeatedly. **Core Idea** - Relax every edge **V-1 times**. - Because the longest simple path has at most `V-1` edges. - Follows DP: "Improves result after each iteration" **Time Complexity:** `O(V × E)` **Space Complexity:** `O(V)` **LeetCode** * [Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops/) * [Network Delay Time (alternative way)](https://leetcode.com/problems/network-delay-time/) **Memory Trick** > Negative edges → Repeat edge relaxation → Bellman–Ford ## 4. Floyd–Warshall **Use when:** * Need shortest path between **every pair of nodes** * Graph is small (n ≤ ~200) * Follows Dynamic Programming: "If you distance from A to B and B to C then you also know distance from A to C" It tries every node as an intermediate: ``` A → B → C ``` **Time Complexity:** `O(V³)` **Space Complexity:** `O(V²)` **LeetCode** * [Find the City With the Smallest Number of Neighbors](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) * [Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/) **Memory Trick** > Everyone checks through everyone → Triple loop → Floyd --- ## The One Pattern Behind All Every shortest path algorithm does the same thing: **Relaxation** ``` if dist[u] + w < dist[v]: update dist[v] ``` Different algorithms only change: * How many times we relax * In what order we relax --- ## Cheat Sheet * “Minimum steps / grid” → BFS * “Minimum time / delay / cost” → Dijkstra * “K stops / negative weight” → Bellman–Ford * “Distance between every pair” → Floyd–Warshall -