Bellman Ford Algorithm Negative Weights in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main purpose of the Bellman Ford algorithm?

The Bellman Ford algorithm finds the shortest path from a single source vertex to all other vertices in a graph, even if the graph has edges with negative weights.

intermediate

How does Bellman Ford handle negative weight edges differently from Dijkstra's algorithm?

Bellman Ford can handle negative weight edges by relaxing all edges multiple times, while Dijkstra's algorithm assumes all edge weights are non-negative and may fail with negative weights.

intermediate

What does it mean if Bellman Ford detects a negative weight cycle?

It means there is a cycle in the graph where the total sum of edge weights is negative, causing the shortest path to be undefined because you can keep going around the cycle to reduce the path cost infinitely.

beginner

How many times does Bellman Ford relax all edges in the graph?

It relaxes all edges exactly |V| - 1 times, where |V| is the number of vertices in the graph.

beginner

What is the time complexity of the Bellman Ford algorithm?

The time complexity is O(V * E), where V is the number of vertices and E is the number of edges in the graph.

What is the first step Bellman Ford algorithm performs on all edges?

A Relax all edges

B Sort edges by weight

C Remove negative edges

D Find cycles

Bellman Ford starts by relaxing all edges to update shortest path estimates.

How many times does Bellman Ford repeat edge relaxation?

A |V| - 1 times

B |V| times

C |E| times

D Until no changes

Bellman Ford relaxes edges |V| - 1 times to ensure shortest paths are found.

What does Bellman Ford do after the relaxation steps to detect negative cycles?

A Removes edges

B Sorts vertices

C Checks if any edge can still be relaxed

D Runs Dijkstra's algorithm

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

Which algorithm cannot handle negative weight edges correctly?

A Bellman Ford

B Floyd Warshall

C Prim's

D Dijkstra

Dijkstra's algorithm assumes non-negative weights and fails with negative edges.

What is the main limitation of Bellman Ford algorithm?

A Cannot detect negative cycles

B Slow for large graphs

C Only works on trees

D Does not find shortest paths

Bellman Ford is slower (O(V*E)) compared to other algorithms like Dijkstra.

Explain how Bellman Ford algorithm detects negative weight cycles in a graph.

Think about what happens if you can still improve shortest paths after all normal relaxations.

Describe the step-by-step process of the Bellman Ford algorithm for finding shortest paths.

Start from setting distances, then repeat edge updates, then check for problems.

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