How to Solve: Bellman-Ford Algorithm (Negative Weights) – Complete Guide for FAANG Interviews

How to Solve: Bellman-Ford Algorithm (Negative Weights) – Complete Guide for FAANG Interviews

? Introduction

"This algorithm appears in 1 out of every 3 FAANG graph interviews—master it, and you’ll detect negative cycles, handle edge cases, and prove you can optimize under constraints when Dijkstra fails."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Bellman-Ford, ensure you understand: 1. Graph Representations (Adjacency List vs. Matrix) 2. Shortest Path Basics (Dijkstra’s Algorithm, Relaxation) 3. Time Complexity Analysis (Big-O notation for nested loops)

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

1. Initialize Distances
2. Set dist[source] = 0, all others to ∞.

3. Initialize prev array (for path reconstruction) with -1.

4. Relax All Edges |V|-1 Times

5. For each edge (u, v, weight), check if dist[u] + weight < dist[v].
6. If true, update dist[v] and set prev[v] = u.

7. Track if any updates occurred in the iteration.

8. Early Termination Check

9. If no updates in an iteration, break early (optimization).

10. Negative Cycle Detection (Optional)

11. Run one extra relaxation pass.

12. If any dist[v] decreases, a negative cycle exists.

13. Return Results

14. If no negative cycle: return dist and prev.
15. If negative cycle detected: return None or raise an error.

? WORKED EXAMPLES

Example 1 – Basic: Shortest Path with Negative Weights

Problem: Given a directed graph with negative weights, find the shortest path from source to all nodes.

Graph:

Edges: [(0,1,4), (0,2,2), (1,2,5), (1,3,10), (2,4,3), (4,3,4), (3,4,5)]
Source: 0

Solution (Python):

def bellman_ford(edges, V, source):

    dist = [float('inf')]  V

    dist[source] = 0

    prev = [-1]  V


    # Relax all edges |V|-1 times

    for _ in range(V - 1):

        updated = False

        for u, v, weight in edges:

            if dist[u] + weight < dist[v]:

                dist[v] = dist[u] + weight

                prev[v] = u

                updated = True

        if not updated:  # Early termination

            break


    # Check for negative cycles

    for u, v, weight in edges:

        if dist[u] + weight < dist[v]:

            return None, None  # Negative cycle detected


    return dist, prev

Time Complexity: O(V E) Space Complexity: O(V)

Why This Works: - Relaxation ensures the shortest path is found after |V|-1 iterations (longest possible path without cycles). - Early termination optimizes best-case scenarios.

Example 2 – Medium: Negative Cycle Detection

Problem: Detect if a graph contains a negative cycle reachable from the source.

Graph:

Edges: [(0,1,1), (1,2,-1), (2,0,-1)]  # Negative cycle: 0→1→2→0
Source: 0

Solution (Python):

def has_negative_cycle(edges, V, source):

    dist = [float('inf')]  V

    dist[source] = 0


    # Relax |V|-1 times

    for _ in range(V - 1):

        for u, v, weight in edges:

            if dist[u] + weight < dist[v]:

                dist[v] = dist[u] + weight


    # Check for negative cycles

    for u, v, weight in edges:

        if dist[u] + weight < dist[v]:

            return True  # Negative cycle exists


    return False

Time Complexity: O(V E) Space Complexity: O(V)

Why This Works: - After |V|-1 relaxations, any further decrease in dist[v] indicates a negative cycle.

Example 3 – Hard: Path Reconstruction with Negative Weights

Problem: Return the shortest path from source to target if no negative cycles exist.

Graph:

Edges: [(0,1,4), (0,2,2), (1,2,1), (1,3,5), (2,3,8), (2,4,10), (3,4,2)]
Source: 0, Target: 4

Solution (Python):

def shortest_path(edges, V, source, target):

    dist = [float('inf')]  V

    dist[source] = 0

    prev = [-1]  V


    # Relax |V|-1 times

    for _ in range(V - 1):

        for u, v, weight in edges:

            if dist[u] + weight < dist[v]:

                dist[v] = dist[u] + weight

                prev[v] = u


    # Check for negative cycles

    for u, v, weight in edges:

        if dist[u] + weight < dist[v]:

            return None  # Negative cycle


    # Reconstruct path

    path = []

    if dist[target] == float('inf'):

        return path  # No path exists


    current = target

    while current != -1:

        path.append(current)

        current = prev[current]

    path.reverse()


    return path

Time Complexity: O(V E) Space Complexity: O(V)

Why This Works: - The prev array tracks the path, and reversing it gives the correct order.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap

"Alright, let’s lock this in. Bellman-Ford is your go-to when Dijkstra fails—negative weights, negative cycles, or dynamic graphs. Here’s the playbook:

1. Initialize: Set dist[source] = 0, others to ∞.
2. Relax: Loop |V|-1 times over all edges. Update dist[v] if a shorter path is found.
3. Early Exit: If no updates, break early.
4. Cycle Check: Run one extra pass. If any dist[v] decreases, a negative cycle exists.
5. Path Reconstruction: Use the prev array to backtrack from the target.

Common pitfalls? Forgetting to initialize the source, skipping the cycle check, or not handling unreachable nodes. Interviewers love asking about negative cycles—so always run that extra pass. Now go crush it!

? Final Notes

• Practice: Implement Bellman-Ford on LeetCode (e.g., 787. Cheapest Flights Within K Stops).
• Follow-Up: Be ready to discuss SPFA (optimized Bellman-Ford) or Johnson’s Algorithm.

You’ve got this! ?