Bellman Ford Algorithm Negative Weights in DSA Python

Mental Model

We find the shortest path from one point to all others even if some paths reduce distance (negative weights). We check all paths multiple times to catch these reductions.

Analogy: Imagine traveling between cities where some roads have toll refunds (negative cost). You keep updating your best route as you discover cheaper ways, even if it means going back and forth.

Graph edges:
A -> B (weight 4)
A -> C (weight 5)
B -> C (weight -3)
C -> D (weight 2)

Initial distances:
A [0] -> B [∞] -> C [∞] -> D [∞]

Dry Run Walkthrough

Input: Graph edges: A->B(4), A->C(5), B->C(-3), C->D(2); start at A

Goal: Find shortest distances from A to all nodes, handling negative weight edge B->C

Step 1: Initialize distances: A=0, others=∞

A[0] -> B[∞] -> C[∞] -> D[∞]

Why: Start with known distance 0 at source, unknown (∞) elsewhere

Step 2: Relax edge A->B: update B distance to 4

A[0] -> B[4] -> C[∞] -> D[∞]

Why: Found a path to B with cost 4, better than ∞

Step 3: Relax edge A->C: update C distance to 5

A[0] -> B[4] -> C[5] -> D[∞]

Why: Found a path to C with cost 5, better than ∞

Step 4: Relax edge B->C: update C distance to 1 (4 + -3)

A[0] -> B[4] -> C[1] -> D[∞]

Why: Negative edge reduces C distance from 5 to 1

Step 5: Relax edge C->D: update D distance to 3 (1 + 2)

A[0] -> B[4] -> C[1] -> D[3]

Why: Found path to D with cost 3

Step 6: Repeat relaxation to confirm no further updates

A[0] -> B[4] -> C[1] -> D[3]

Why: No changes means shortest paths found

Result:

A[0] -> B[4] -> C[1] -> D[3]

Annotated Code

DSA Python

class Edge:
    def __init__(self, src, dest, weight):
        self.src = src
        self.dest = dest
        self.weight = weight

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.edges = []

    def add_edge(self, src, dest, weight):
        self.edges.append(Edge(src, dest, weight))

    def bellman_ford(self, start):
        dist = {v: float('inf') for v in self.V}
        dist[start] = 0

        for _ in range(len(self.V) - 1):
            updated = False
            for edge in self.edges:
                if dist[edge.src] != float('inf') and dist[edge.src] + edge.weight < dist[edge.dest]:
                    dist[edge.dest] = dist[edge.src] + edge.weight
                    updated = True
            if not updated:
                break

        # Check for negative weight cycles
        for edge in self.edges:
            if dist[edge.src] != float('inf') and dist[edge.src] + edge.weight < dist[edge.dest]:
                return "Graph contains negative weight cycle"

        return dist

# Driver code
vertices = ['A', 'B', 'C', 'D']
g = Graph(vertices)
g.add_edge('A', 'B', 4)
g.add_edge('A', 'C', 5)
g.add_edge('B', 'C', -3)
g.add_edge('C', 'D', 2)

result = g.bellman_ford('A')
if isinstance(result, dict):
    for vertex in vertices:
        print(f"Distance from A to {vertex}: {result[vertex]}")
else:
    print(result)

dist = {v: float('inf') for v in self.V} dist[start] = 0

Initialize distances with infinity except start node at 0

for _ in range(len(self.V) - 1):

Repeat relaxation for V-1 times to ensure shortest paths

for edge in self.edges: if dist[edge.src] != float('inf') and dist[edge.src] + edge.weight < dist[edge.dest]: dist[edge.dest] = dist[edge.src] + edge.weight updated = True

Relax edges: update distance if shorter path found

if not updated: break

Stop early if no distance updates in this iteration

for edge in self.edges: if dist[edge.src] != float('inf') and dist[edge.src] + edge.weight < dist[edge.dest]: return "Graph contains negative weight cycle"

Detect negative weight cycle if any edge can still relax

Output

Distance from A to A: 0

Distance from A to B: 4

Distance from A to C: 1

Distance from A to D: 3

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times where V is vertices and E is edges

Space: O(V) for storing distances to each vertex

vs Alternative: Unlike Dijkstra which fails with negative weights, Bellman-Ford handles them but is slower due to repeated edge relaxation

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and returns error message

DSA Python

for edge in self.edges:
    if dist[edge.src] != float('inf') and dist[edge.src] + edge.weight < dist[edge.dest]:
        return "Graph contains negative weight cycle"

Graph with no edges

Distances remain infinity except start node at 0

DSA Python

dist = {v: float('inf') for v in self.V}
dist[start] = 0

Single vertex graph

Distance to itself is 0, no edges to relax

DSA Python

dist = {v: float('inf') for v in self.V}
dist[start] = 0

When to Use This Pattern

When you need shortest paths but edges can have negative weights, use Bellman-Ford to safely find shortest distances or detect negative cycles.

Common Mistakes

Mistake: Not repeating edge relaxation V-1 times, missing updates from longer paths
Fix: Always loop V-1 times to ensure all shortest paths are found

Mistake: Not checking for negative weight cycles after relaxation
Fix: Add a final check to detect if any edge can still relax, indicating a negative cycle

Summary

Finds shortest paths from one node to all others even with negative edge weights.

Use when graph edges can have negative weights but no negative cycles.

Repeatedly relax edges to update shortest distances, detecting negative cycles if present.

Practice

1. What is the main purpose of the Bellman-Ford algorithm when dealing with graphs that have negative edge weights?

easy

A. To sort vertices in topological order

B. To find the longest path in a graph

C. To detect cycles in an undirected graph

D. To find the shortest path from a single source to all vertices, even with negative weights

Solution

1. Step 1: Understand Bellman-Ford's goal

   The Bellman-Ford algorithm is designed to find shortest paths from one source vertex to all other vertices in a graph, even if some edges have negative weights.

2. Step 2: Compare with other algorithms

   Unlike Dijkstra's algorithm, Bellman-Ford can handle negative weights and also detect negative weight cycles.

3. Final Answer:

   To find the shortest path from a single source to all vertices, even with negative weights -> Option D

4. Quick Check:

   Bellman-Ford finds shortest paths with negative weights [OK]

Hint: Bellman-Ford handles negative edges for shortest paths [OK]

Common Mistakes:

• Confusing Bellman-Ford with Dijkstra's algorithm
• Thinking it finds longest paths
• Assuming it only detects cycles

2. Which of the following is the correct way to initialize the distance array in Bellman-Ford algorithm in Python for a graph with vertices numbered 0 to n-1 and source vertex src?

easy

A. dist = [float('inf')] * n; dist[src] = 0

B. dist = [0] * n; dist[src] = float('inf')

C. dist = [null] * n; dist[src] = 0

D. dist = [float('inf')] * n; dist[0] = 0

Solution

1. Step 1: Initialize distances to infinity

   We set all distances to infinity to represent unknown paths initially.

2. Step 2: Set source distance to zero

   The distance from the source vertex to itself is zero, so dist[src] = 0.

3. Final Answer:

   dist = [float('inf')] * n; dist[src] = 0 -> Option A

4. Quick Check:

   Initialize all to infinity, source to zero [OK]

Hint: Set all distances to infinity, source to zero [OK]

Common Mistakes:

• Setting all distances to zero
• Setting source distance to infinity
• Using null instead of infinity

3. What will be the output distances array after running Bellman-Ford on the following graph with source vertex 0? Edges: [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)]

n = 4
edges = [(0,1,4), (0,2,5), (1,2,-3), (2,3,4)]
src = 0

medium

A. [0, 4, 5, 9]

B. [0, 4, 1, 9]

C. [0, 4, 1, 5]

D. [0, 5, 2, 6]

Solution

1. Step 1: Initialize distances

   dist = [0, inf, inf, inf]

2. Step 2: Relax edges repeatedly

   Iteration 1: dist[1] = 4, dist[2] = 5; then dist[2] = min(5, 4 + (-3)) = 1; dist[3] = dist[2] + 4 = 5 Iteration 2: No further updates

3. Final Answer:

   [0, 4, 1, 5] -> Option C

4. Quick Check:

   Relax edges 3 times, get distances [0,4,1,5] [OK]

Hint: Relax edges n-1 times, update distances [OK]

Common Mistakes:

• Not updating dist[2] with negative edge
• Calculating dist[3] incorrectly
• Stopping relaxation too early

4. Consider the following code snippet for Bellman-Ford. What is the error?

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

medium

A. The outer loop should run n-1 times, not n times

B. The distance initialization is incorrect

C. The edge relaxation condition is wrong

D. The function does not return the path, only distances

Solution

1. Step 1: Check loop iterations

   Bellman-Ford requires relaxing edges exactly n-1 times to guarantee shortest paths.

2. Step 2: Identify the error

   The code runs the outer loop n times, which is one extra iteration and can cause incorrect detection of negative cycles or unnecessary work.

3. Final Answer:

   The outer loop should run n-1 times, not n times -> Option A

4. Quick Check:

   Outer loop runs n-1 times [OK]

Hint: Relax edges exactly n-1 times [OK]

Common Mistakes:

• Running outer loop n times instead of n-1
• Misinitializing distances
• Confusing relaxation condition

5. Given a graph with edges [(0,1,1), (1,2,-1), (2,0,-1)], what will Bellman-Ford detect when run from source 0, and why?

hard

A. It will return infinite distances for all vertices

B. It will detect a negative weight cycle because the cycle sum is negative

C. It will raise an error due to invalid edges

D. It will find shortest paths without issues

Solution

1. Step 1: Calculate cycle weight sum

   The cycle is 0->1->2->0 with weights 1 + (-1) + (-1) = -1, which is negative.

2. Step 2: Understand Bellman-Ford behavior

   Bellman-Ford detects negative weight cycles by checking for further relaxation after n-1 iterations.

3. Step 3: Conclusion

   Since the cycle sum is negative, Bellman-Ford will detect this negative weight cycle.

4. Final Answer:

   It will detect a negative weight cycle because the cycle sum is negative -> Option B

5. Quick Check:

   Negative cycle sum triggers detection [OK]

Hint: Negative cycle sum means Bellman-Ford detects cycle [OK]

Common Mistakes:

• Assuming no negative cycles exist
• Thinking algorithm crashes on negative cycles
• Confusing cycle detection with path finding