The Core Idea
Not All Graphs Are the Same Problem
'Find the shortest path' sounds like one problem, but the correct algorithm depends entirely on what kind of graph you're navigating. An unweighted graph (every edge costs the same) is a completely different problem from a weighted graph (edges have different costs), and a graph with negative edge weights is different again — because 'shortest' in a graph with negative weights can behave in surprising, even undefined, ways if a negative cycle exists.
This is why shortest-path algorithms are always taught as a set of three, in order of increasing generality: each one handles a case the previous one can't, at the cost of being slower.
💡 Memory Trick
BFS is a crowd spreading out evenly from one person, ripple by ripple — everyone the same 'distance' apart, so the first ripple to reach you is the shortest path. DIJKSTRA is that same crowd, but now some steps take longer than others, so you always let whoever is currently closest take the next step, keeping the crowd's frontier growing in true cost order. BELLMAN-FORD is more paranoid — it deliberately re-checks every path multiple times because in this version, some steps can wormhole you cost backward, and BFS/Dijkstra's greedy shortcuts fall apart.
The Three Algorithms
How Each One Handles Its Graph Type
1
Breadth-First Search (BFS) — O(V + E)
Used exclusively for unweighted graphs, where every edge counts as one step. BFS explores the graph level by level, using a queue, guaranteeing the first time you reach a node is via the shortest possible number of edges. It cannot handle weighted edges correctly — it only counts hops, not cost.
Example: finding the fewest number of connections between two people in a social network.
2
Dijkstra's Algorithm — O((V + E) log V)
Used for weighted graphs where all edge weights are non-negative. Using a priority queue (min-heap), it always expands the currently-closest unvisited node next, guaranteeing that once a node's shortest distance is finalized, it will never be improved later. This greedy guarantee is exactly what fails if negative weights are allowed.
Example: GPS routing where road segments have different travel times, all positive.
3
Bellman-Ford — O(V × E)
Used when negative edge weights are possible. Instead of greedily finalizing distances, it relaxes (rechecks) every single edge, V-1 times total, allowing distances to keep improving as better paths are discovered. A final extra pass can detect a negative cycle (a loop that keeps reducing total cost forever, making 'shortest path' undefined).
Example: financial arbitrage graphs, where an edge weight represents a currency exchange rate that can effectively be negative (a gain) in log-space.
Choosing the Right One
Matching Algorithm to Graph Type
The decision is a simple two-question filter: does the graph have weights at all? If not, BFS. Do any weights go negative? If not, Dijkstra. If yes, Bellman-Ford. There's a real cost to over-choosing: running Bellman-Ford on a simple non-negative graph works correctly but wastes time, since it doesn't exploit the greedy shortcut Dijkstra can safely take.
A fourth related algorithm, Floyd-Warshall, computes shortest paths between every pair of nodes at once (O(V³)) rather than from a single source — useful when you need the full distance matrix rather than paths from one starting point.
🖥️ Applied Scenario
You're building a delivery-route optimizer where road segments have travel times, and a promotional feature temporarily gives a 'refund' (negative cost) on certain toll roads.
1
You first consider Dijkstra's algorithm since most edges are simple positive travel times, but you realize the toll refund creates at least one negative edge weight in the graph.
2
You recall that Dijkstra's greedy 'finalize the closest node' strategy breaks down if any edge weight is negative — it can produce an incorrect shortest path.
3
You switch to Bellman-Ford, which correctly handles negative edges by repeatedly relaxing all edges rather than greedily finalizing distances early.
4
Conclusion: you also run Bellman-Ford's negative-cycle check to confirm no combination of refunded toll roads creates an infinite-value loop, which would make 'shortest route' meaningless.
📌 Exam Application
Exam questions frequently ask you to identify which algorithm applies given a described graph (weighted vs. unweighted, negative weights present or not), and to state each algorithm's time complexity. You may also be asked to explain, conceptually, why Dijkstra fails with negative weights — the answer is that Dijkstra assumes a node's shortest distance is finalized once visited, but a later negative edge could still improve it, and Dijkstra's greedy structure never revisits finalized nodes.
⚠️ Most Common Shortest Path Algorithms Mistakes
The most common mistake is using Dijkstra on a graph with negative weights, producing a wrong answer without any error or warning — Dijkstra doesn't detect that its assumption has been violated. Another frequent error is applying BFS to a weighted graph, assuming 'fewest edges' is the same as 'lowest total cost' — they are only the same when every edge has equal weight.
✓ Quick Self-Test
Given a graph description, can you correctly identify whether BFS, Dijkstra, or Bellman-Ford applies, and justify your choice in one sentence? Can you explain why a negative cycle makes 'shortest path' undefined rather than just very negative?
→
← All Algorithms Lessons