Bellman Ford Algorithm Negative Weights in DSA Python - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest path from a starting city to all other cities. Some roads have toll discounts, which means the cost can be negative. You will use the Bellman Ford algorithm to handle these negative weights safely.

🎯 Goal: Build a program that uses the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities, even when some roads have negative costs.

📋 What You'll Learn

Create a list of edges representing roads with start city, end city, and cost

Set up a distance list to store shortest distances from the start city

Implement the Bellman Ford algorithm to update distances

Print the final shortest distances from the start city to all other cities

💡 Why This Matters

🌍 Real World

Navigation systems and routing software often need to find shortest paths even when some roads have discounts or penalties, which can be represented as negative weights.

💼 Career

Understanding Bellman Ford algorithm is important for roles in software engineering, especially in fields like logistics, network routing, and game development where pathfinding with negative weights is required.

1

Create the graph edges

Create a list called edges with these exact tuples representing roads: (0, 1, 5), (1, 2, 20), (1, 5, 30), (5, 3, -15), (3, 2, -10), (2, 4, 75)

DSA Python

# Your code here

Hint

Use a list of tuples where each tuple has three numbers: start city, end city, and cost.

2

Initialize distances

Create a list called distances with 6 elements, all set to float('inf'), then set distances[0] to 0 because city 0 is the start city

DSA Python

edges = [(0, 1, 5), (1, 2, 20), (1, 5, 30), (5, 3, -15), (3, 2, -10), (2, 4, 75)]
# Your code here

Hint

Use float('inf') to represent unknown distances and set the start city distance to 0.

3

Implement Bellman Ford algorithm

Write a for loop that runs 5 times, and inside it use a for loop over edges with variables u, v, w. Update distances[v] to distances[u] + w if it is smaller than the current distances[v]

DSA Python

edges = [(0, 1, 5), (1, 2, 20), (1, 5, 30), (5, 3, -15), (3, 2, -10), (2, 4, 75)]
distances = [float('inf')] * 6
distances[0] = 0
# Your code here

Hint

Relax all edges 5 times to find shortest paths, checking if the new path is shorter before updating.

4

Print shortest distances

Write print(distances) to display the final shortest distances from city 0 to all other cities

DSA Python

edges = [(0, 1, 5), (1, 2, 20), (1, 5, 30), (5, 3, -15), (3, 2, -10), (2, 4, 75)]
distances = [float('inf')] * 6
distances[0] = 0
for _ in range(5):
    for u, v, w in edges:
        if distances[u] != float('inf') and distances[u] + w < distances[v]:
            distances[v] = distances[u] + w
# Your code here

Hint

Print the distances list to see the shortest path costs from city 0.

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