Why Bellman Ford Algorithm Negative Weights in DSA Python?

The Big Idea

What if some roads actually pay you to travel them? How do you find the cheapest path then?

The Scenario

Imagine you are planning a road trip across many cities. Some roads have tolls (positive costs), but some roads offer discounts or cashback (negative costs). You want to find the cheapest way to reach each city from your starting point.

The Problem

Trying to calculate the cheapest path manually is very hard when some roads reduce your total cost. Simple methods like always picking the shortest road first can fail or get stuck in loops, making it impossible to find the best route.

The Solution

The Bellman Ford algorithm smartly handles roads with negative costs by repeatedly relaxing the paths. It checks all roads multiple times to find the cheapest cost to each city, even if some roads reduce the total cost. It also detects if there is a loop that keeps reducing cost endlessly.

Before vs After

✗ Before

distances = {city: float('inf') for city in cities}
distances[start] = 0
# Trying to update distances once, ignoring negative roads
for road in roads:
    if distances[road.start] + road.cost < distances[road.end]:
        distances[road.end] = distances[road.start] + road.cost

✓ After

distances = {city: float('inf') for city in cities}
distances[start] = 0
for _ in range(len(cities) - 1):
    for road in roads:
        if distances[road.start] + road.cost < distances[road.end]:
            distances[road.end] = distances[road.start] + road.cost

What It Enables

This algorithm enables finding the cheapest paths even when some roads reduce your total travel cost, and warns if there is a harmful loop of discounts.

Real Life Example

In finance, Bellman Ford helps find the best currency exchange path when some exchanges offer better rates (negative costs), and detects if there is an arbitrage loop to make infinite profit.

Key Takeaways

Manual shortest path methods fail with negative costs.

Bellman Ford repeatedly updates paths to handle negative weights.

It detects negative loops that cause endless cost reduction.

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