Bellman Ford Algorithm Negative Weights in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance to the source vertex as zero.

DSA Python

dist = [float('inf')] * V
dist[[1]] = 0

Drag options to blanks, or click blank then click option'

AV

B1

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance of a wrong vertex to zero.

Using negative index for source vertex.

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

2fill in blank

medium

Complete the code to relax edges inside the main loop.

DSA Python

for _ in range(V - 1):
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w [1] dist[v]:
            dist[v] = dist[u] + w

Drag options to blanks, or click blank then click option'

A>

B!=

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < in the condition.

Not checking if dist[u] is infinity.

Relaxation updates dist[v] if a shorter path is found, so we check if dist[u] + w < dist[v].

3fill in blank

hard

Fix the error in the negative cycle detection condition.

DSA Python

for u, v, w in edges:
    if dist[u] != float('inf') and dist[u] + w [1] dist[v]:
        return True  # Negative cycle detected

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= or > instead of < in the condition.

Not checking if dist[u] is infinity.

If after V-1 relaxations, dist[u] + w < dist[v], it means a negative cycle exists.

4fill in blank

hard

Fill both blanks to complete the relaxation update and condition.

DSA Python

for _ in range(V - 1):
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w [1] dist[v]:
            dist[v] = dist[u] [2] w

Drag options to blanks, or click blank then click option'

A<

B+

C-

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < in condition.

Using - instead of + for updating distance.

Relax if dist[u] + w < dist[v], then update dist[v] = dist[u] + w.

5fill in blank

hard

Fill all three blanks to complete the negative cycle detection and return statement.

DSA Python

for u, v, w in edges:
    if dist[u] != float('inf') and dist[u] + w [1] dist[v]:
        print('Graph contains a negative weight cycle')
        return [2]
return [3]

Drag options to blanks, or click blank then click option'

A>

BTrue

CFalse

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < in condition.

Returning False when cycle is detected.

If dist[u] + w < dist[v], negative cycle exists, so return True; otherwise, return False.

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