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

Introduction to Shortest Path Algorithms

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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)$).

Engineering Standard: The "Staff" Perspective

In high-throughput distributed systems, the code we write is often the easiest part. The difficulty lies in how that code interacts with other components in the stack.

1. Data Integrity and The "P" in CAP

Whenever you are dealing with state (Databases, Caches, or In-memory stores), you must account for Network Partitions. In a standard Java microservice, we often choose Availability (AP) by using Eventual Consistency patterns. However, for financial ledgers, we must enforce Strong Consistency (CP), which usually involves distributed locks (Redis Redlock or Zookeeper) or a strictly linearizable sequence.

2. The Observability Pillar

Writing logic without observability is like flying a plane without a dashboard. Every production service must implement:

• Tracing (OpenTelemetry): Track a single request across 50 microservices.
• Metrics (Prometheus): Monitor Heap usage, Thread saturation, and P99 latencies.
• Structured Logging (ELK/Splunk): Never log raw strings; use JSON so you can query logs like a database.

3. Production Incident Prevention

To survive a 3:00 AM incident, we use:

• Circuit Breakers: Stop the bleeding if a downstream service is down.
• Bulkheads: Isolate thread pools so one failing endpoint doesn't crash the entire app.
• Retries with Exponential Backoff: Avoid the "Thundering Herd" problem when a service comes back online.

Critical Interview Nuance

When an interviewer asks you about this topic, don't just explain the code. Explain the Trade-offs. A Staff Engineer is someone who knows that every architectural decision is a choice between two "bad" outcomes. You are picking the one that aligns with the business goal.

Performance Checklist for High-Load Systems:

1. Minimize Object Creation: Use primitive arrays and reusable buffers.
2. Batching: Group 1,000 small writes into 1 large batch to save I/O cycles.
3. Async Processing: If the user doesn't need the result immediately, move it to a Message Queue (Kafka/SQS).

Key Takeaways

• Pop the node u with the smallest distance.
• For every neighbor v of u:
• If dist[u] + weight(u, v) < dist[v]:

Read Next

• MANG Problem #41: Making A Large Island (Hard)
• MANG Problem #42: Design In-Memory File System (Hard)
• DSA Masterclass Module 1: Time & Space Complexity