Dijkstra vs BFS vs Bellman-Ford

You should always use Breadth-First Search for unweighted graphs, Dijkstra for non-negative edge weights, and Bellman-Ford only when negative edge weights exist. Picking the wrong shortest path algorithm in an interview wastes time rewriting code when the constraints demand a specific approach.

Why BFS Fails on Weighted Graphs

Breadth-First Search assumes that the first time you visit a node, you have found the shortest path to it. This assumption holds true when every edge has a weight of 1 or every edge weight is identical. Consider a graph where node A connects to node B with an edge weight of 10 and to node C with an edge weight of 1. Node C connects directly to node B with a weight of 1. BFS pushes C onto the queue first because it sits 1 step away, while B sits 1 step away too if you count hops, but the actual path cost to B via C is 2. BFS records a cost of 10 for B prematurely because it ignores edge weights.

Use standard BFS for unweighted grid traversal problems like rotting oranges or finding the minimum knight moves on an 8x8 chessboard. The time complexity stays O(V + E) because each vertex and edge enters the queue once.

When Dijkstra Breaks Down

Dijkstra relies on a priority queue to greedily pick the closest unvisited node. It fails entirely when your graph contains a negative edge weight. Suppose you have node A, B, and C. The edge from A to B costs 5, A to C costs 2, and C to B costs -10. Dijkstra visits C first with distance 2, marks C as finalized, and then computes the distance to B as 5. It misses the cheaper path through C that totals -8. Once Dijkstra marks a node as visited, it never updates that node again.

Use Dijkstra for problems like network delay time or finding the cheapest flight with k stops when all ticket prices are positive integers. The time complexity is O(E log V) using a binary heap, which easily passes within standard time limits for V = 100000.

Handling Negative Edges With Bellman-Ford

Bellman-Ford relaxes all E edges V - 1 times. This brute-force relaxation guarantees correctness even with negative edge weights because the longest possible simple path in a graph with V vertices contains V - 1 edges. If you run one more relaxation pass and any distance value still decreases, a negative weight cycle exists.

Run Bellman-Ford when an interview problem explicitly mentions debt settlement or currency arbitrage where exchange rates convert into negative logarithmic weights. The time complexity is O(V times E), which runs slowly on large graphs, so never apply it unless negative weights appear in the input constraints.

The Special Case of 0-1 BFS

When edge weights only equal 0 or 1, standard Dijkstra with a priority queue adds unnecessary logarithmic overhead. Use a double-ended queue instead. Push nodes with 0 weight to the front and nodes with 1 weight to the back.

Consider a grid where moving right costs 0 and moving down costs 1. Popping from the front for 0 weight edges keeps the queue sorted by distance without a heap. The time complexity drops to strict O(V + E). This optimization frequently separates candidates who pass all hidden test cases from those who get Time Limit Exceeded on grid navigation questions.

A Hand-Calculated Dijkstra Example

Take a graph with 4 nodes: 0, 1, 2, 3. Edges exist from 0 to 1 with weight 4, 0 to 2 with weight 1, 2 to 1 with weight 2, and 1 to 3 with weight 1.

Initialize the distance array as [0, infinity, infinity, infinity].

1. Pop node 0 with distance 0. Relax its neighbors. Distance to 1 becomes min(infinity, 0 + 4) = 4. Distance to 2 becomes min(infinity, 0 + 1) = 1. Distance array is [0, 4, 1, infinity].
2. Pop node 2 with distance 1. Relax its neighbor 1. Distance to 1 becomes min(4, 1 + 2) = 3. Distance array is [0, 3, 1, infinity].
3. Pop node 1 with distance 3. Relax its neighbor 3. Distance to 3 becomes min(infinity, 3 + 1) = 4. Distance array is [0, 3, 1, 4].
4. Pop node 3 with distance 4. It has no outgoing edges.

The shortest path from 0 to 3 costs 4, following the path 0 to 2 to 1 to 3.

The Rule of Thumb

Weights all 1?           -> Use BFS O(V + E)
Weights 0 or 1?          -> Use 0-1 BFS O(V + E)
Weights non-negative?    -> Use Dijkstra O(E log V)
Negative weights exist?  -> Use Bellman-Ford O(V * E)

Practice these implementations on DSA Tracker before your next coding round.

---

Keep going with practice problems and the online compiler.

Further reading: Breadth-first search on Wikipedia.