Bellman Ford Algorithm Negative Weights in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bellman-Ford on a graph with negative edges

What is the output distances array after running Bellman-Ford on this graph from source 0?

DSA Python

edges = [(0, 1, 4), (0, 2, 5), (1, 2, -3), (2, 3, 4), (3, 1, 6)]
V = 4
source = 0

def bellman_ford(edges, V, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

result = bellman_ford(edges, V, source)
print(result)

A [0, -2, 1, 5]

B [0, 4, 5, 9]

C [0, 4, 1, 5]

D [0, 4, 1, 9]

💡 Hint

Remember Bellman-Ford relaxes edges V-1 times and updates distances if a shorter path is found.

The algorithm updates distances step by step. The negative edge from 1 to 2 reduces distance to 2 to 1. Then 2 to 3 updates distance to 5. The final distances are [0, 4, 1, 5].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

Which statement correctly describes how Bellman-Ford detects a negative weight cycle?

A Bellman-Ford cannot detect negative weight cycles.

B If the graph has any negative edge, Bellman-Ford always detects a negative cycle.

C Bellman-Ford detects negative cycles by checking if distances become infinite.

D If after V-1 iterations, any edge can still be relaxed, a negative weight cycle exists.

💡 Hint

Think about what happens if distances keep decreasing after all relaxations.

After V-1 iterations, if any edge can still reduce a distance, it means a cycle with negative total weight exists.

🔧 Debug

advanced

Identify the error in this Bellman-Ford implementation

What error will this code produce or what is wrong with it?

DSA Python

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

edges = [(0, 1, 1), (1, 2, 2)]
print(bellman_ford(edges, 3, 0))

A Runs but returns incorrect distances because it iterates V times instead of V-1

B Raises IndexError because of wrong loop range

C Runs correctly and returns [0, 1, 3]

D Raises TypeError because dist[u] can be inf and inf + w is invalid

💡 Hint

Check what happens when dist[u] is infinity and you add w to it.

Adding a number to float('inf') is valid in Python, but the code misses a check if dist[u] is infinity before adding w, which can cause wrong comparisons or logic errors.

❓ Predict Output

advanced

Output after detecting negative cycle

What will the output be after running this Bellman-Ford code on a graph with a negative cycle?

DSA Python

edges = [(0, 1, 1), (1, 2, -1), (2, 0, -1)]
V = 3
source = 0

def bellman_ford(edges, V, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return 'Negative cycle detected'
    return dist

print(bellman_ford(edges, V, source))

A Negative cycle detected

B [0, 1, 0]

C [0, 1, -1]

D [0, 0, 0]

💡 Hint

Check the final loop that detects if any edge can still be relaxed.

The cycle 0->1->2->0 has negative total weight, so after V-1 relaxations, edges can still be relaxed, triggering the negative cycle detection.

🚀 Application

expert

Minimum number of iterations to detect negative cycle

Given a graph with V vertices and a negative weight cycle reachable from the source, what is the minimum number of edge relaxation iterations Bellman-Ford needs to detect the cycle?

A At most V-1 iterations

B Exactly V iterations

C At least V iterations

D Exactly 2*V iterations

💡 Hint

Think about how Bellman-Ford uses V-1 iterations to find shortest paths and one extra iteration to detect cycles.

Bellman-Ford relaxes edges V-1 times to find shortest paths. The V-th iteration is used to check if any edge can still be relaxed, indicating a negative cycle.

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