DSA Masterclass: Dijkstra’s vs. Bellman-Ford (Shortest Path Algorithms)

Introduction to Shortest Path Algorithms

Finding the shortest path between two points is one of the most practical applications of Graph Theory. From Google Maps to routing data packets on the internet, shortest path algorithms are everywhere.

In FAANG interviews, you aren't just expected to implement these algorithms; you're expected to know when to use which one. The two heavyweights are Dijkstra’s and Bellman-Ford.

1. Dijkstra’s Algorithm: The Greedy Efficient

Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative weights.

How it works

It uses a Greedy approach and a Priority Queue (Min-Heap).

1. Initialize distances to all nodes as infinity, source as 0.
2. Push {0, source} to the Priority Queue.
3. While the queue is not empty:
   • Pop the node u with the smallest distance.
   • For every neighbor v of u:
     • If dist[u] + weight(u, v) < dist[v]:
       • Update dist[v] and push {dist[v], v} to the queue.

Java Implementation

public int[] dijkstra(int n, List<List<Edge>> adj, int src) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{src, 0});

    while (!pq.isEmpty()) {
        int[] current = pq.poll();
        int u = current[0];
        int d = current[1];

        if (d > dist[u]) continue;

        for (Edge edge : adj.get(u)) {
            if (dist[u] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[u] + edge.weight;
                pq.offer(new int[]{edge.to, dist[edge.to]});
            }
        }
    }
    return dist;
}

Complexity

• Time: $O((E + V) \log V)$ with a Binary Heap.
• Space: $O(V)$.

2. Bellman-Ford Algorithm: The Robust Survivor

Bellman-Ford also finds the shortest path from a source, but it can handle negative weights and detect negative cycles.

How it works

It uses Dynamic Programming principles and "Relaxes" every edge $V-1$ times.

1. Initialize distances to all nodes as infinity, source as 0.
2. For $i = 1$ to $V-1$:
   • For every edge $(u, v)$ with weight $w$:
     • If dist[u] + w < dist[v], then dist[v] = dist[u] + w.
3. Check for Negative Cycles: Run the loop one more time. If any distance still decreases, a negative cycle exists.

Complexity

• Time: $O(V \times E)$.
• Space: $O(V)$.

Dijkstra vs. Bellman-Ford: The Interview Decision Matrix

When to use which?

• Interviewer says: "Find the shortest path in a graph where all weights are 1."
  • Response: "I'll use BFS, as it is $O(V + E)$, more efficient than Dijkstra's."
• Interviewer says: "Find the shortest path where weights are non-negative."
  • Response: "I'll use Dijkstra's with a Priority Queue for $O(E \log V)$ efficiency."
• Interviewer says: "The graph might have negative weights."
  • Response: "I'll use Bellman-Ford, as Dijkstra's can give incorrect results or enter infinite loops with negative cycles."

Practice Problems

1. Network Delay Time (LeetCode 743) - Core Dijkstra
2. Cheapest Flights Within K Stops (LeetCode 787) - Modified Dijkstra or Bellman-Ford
3. Path with Maximum Probability (LeetCode 1514) - Dijkstra variation

Final Takeaways

• Dijkstra is your fast default for positive weights.
• Bellman-Ford is your slow but robust option for negative weights.
• Always check for the "Unit Weight" case (use BFS) or "DAG" case (use Topological Sort + DP for $O(V + E)$).

Read Next

• DSA Masterclass: Topological Sort (Kahn's Algorithm)
• DSA Masterclass: Trie (Prefix Tree)
• System Design: Designing a Distributed Message Queue