Bellman-Ford algorithm in Data Structures Theory - Mini Project: Build & Apply

Bellman-Ford Algorithm Step-by-Step

📖 Scenario: You are working with a weighted graph representing a network of cities connected by roads. Some roads have negative tolls (rebates), and you want to find the shortest path from a starting city to all other cities, even if some roads reduce the total cost.

🎯 Goal: Build the Bellman-Ford algorithm step-by-step to find the shortest distances from a starting city to all other cities in the graph.

📋 What You'll Learn

Create a graph as a list of edges with exact weights

Set up a distance list with initial values

Implement the relaxation step of Bellman-Ford algorithm

Detect negative weight cycles and finalize the shortest distances

💡 Why This Matters

🌍 Real World

Bellman-Ford algorithm is used in network routing protocols to find shortest paths even when some links have negative costs.

💼 Career

Understanding Bellman-Ford helps in roles involving network design, optimization, and algorithm development.

1

Create the graph as a list of edges

Create a variable called edges as a list of tuples representing the graph edges. Each tuple should have three elements: source city index, destination city index, and weight of the edge. Use these exact edges: (0, 1, 5), (0, 2, 4), (1, 3, 3), (2, 1, 6), (3, 2, -2).

Data Structures Theory

# Create the list of edges called edges
# Your code here

Hint

Think of the graph as a list where each item shows a road from one city to another with a cost.

2

Initialize the distance list

Create a list called distance with 4 elements (one for each city). Set the distance of the starting city (index 0) to 0 and all others to a large number (like 9999) to represent infinity.

Data Structures Theory

edges = [(0, 1, 5), (0, 2, 4), (1, 3, 3), (2, 1, 6), (3, 2, -2)]
# Initialize distance list with 0 for start city and 9999 for others
# Your code here

Hint

Distance to the start city is zero because you are already there; others are set high to show they are not reached yet.

3

Relax edges to update distances

Write a for loop that repeats 3 times (number of cities minus one). Inside it, write a nested for loop that goes through each source, destination, and weight in edges. Update distance[destination] if distance[source] + weight is less than the current distance[destination].

Data Structures Theory

edges = [(0, 1, 5), (0, 2, 4), (1, 3, 3), (2, 1, 6), (3, 2, -2)]
distance = [0, 9999, 9999, 9999]
# Relax edges 3 times to update distances
# Your code here

Hint

This step tries to find shorter paths by checking all roads multiple times.

4

Check for negative weight cycles and finalize

Add a for loop over source, destination, and weight in edges. Inside, check if distance[source] + weight < distance[destination]. If true, set a variable has_negative_cycle to True. Otherwise, set it to False before the loop. This detects if a negative cycle exists. Finally, create a variable final_distances and assign it the current distance list.

Data Structures Theory

edges = [(0, 1, 5), (0, 2, 4), (1, 3, 3), (2, 1, 6), (3, 2, -2)]
distance = [0, 9999, 9999, 9999]
for _ in range(3):
    for source, destination, weight in edges:
        if distance[source] + weight < distance[destination]:
            distance[destination] = distance[source] + weight
# Detect negative weight cycle and finalize distances
# Your code here

Hint

This step checks if the graph has a negative cycle that makes shortest paths impossible.

Practice

1. What is the primary purpose of the Bellman-Ford algorithm in graph theory?

easy

A. To sort vertices in topological order

B. To find the minimum spanning tree of 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 edge 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.

2. Step 2: Recognize its unique feature

   Unlike some algorithms, Bellman-Ford can handle graphs with negative edge weights and detect negative weight cycles.

3. Final Answer:

   To find the shortest path from a single source to all vertices, even with negative edge weights -> Option D

4. Quick Check:

   Bellman-Ford finds shortest paths with negative edges = A [OK]

Hint: Bellman-Ford handles negative edges and finds shortest paths [OK]

Common Mistakes:

• Confusing Bellman-Ford with algorithms for minimum spanning trees
• Thinking it only works with positive edge weights
• Assuming it sorts vertices or detects cycles in undirected graphs

2. Which of the following is the correct step repeated in the Bellman-Ford algorithm?

easy

A. Relax all edges |V|-1 times

B. Relax all edges once

C. Relax edges only if weights are positive

D. Relax edges in topological order

Solution

1. Step 1: Recall the relaxation process

   Bellman-Ford repeatedly relaxes all edges to update shortest path estimates.

2. Step 2: Identify the number of repetitions

   It performs this relaxation exactly |V|-1 times, where |V| is the number of vertices.

3. Final Answer:

   Relax all edges |V|-1 times -> Option A

4. Quick Check:

   Relax edges |V|-1 times = D [OK]

Hint: Relax edges |V|-1 times to find shortest paths [OK]

Common Mistakes:

• Relaxing edges only once
• Relaxing edges only if weights are positive
• Assuming topological order is required

3. Consider the graph with edges and weights:
A -> B (4), A -> C (5), B -> C (-3), C -> D (2)
Using Bellman-Ford from vertex A, what is the shortest distance to vertex C?

medium

A. 5

B. 1

C. -3

D. 4

Solution

1. Step 1: Initialize distances from A

   Distance to A=0, B=∞, C=∞, D=∞ initially.

2. Step 2: Relax edges repeatedly

   First relaxation: A->B=4, A->C=5. Then B->C updates C to 4 + (-3) = 1. C->D updates D to 1 + 2 = 3.

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Shortest path A->B->C = 4 + (-3) = 1 [OK]

Hint: Check paths through neighbors to update shortest distances [OK]

Common Mistakes:

• Ignoring negative edge from B to C
• Taking direct edge A->C without relaxation
• Confusing edge weights with distances

4. You run Bellman-Ford on a graph and after |V|-1 iterations, you find an edge u -> v where distance[u] + weight(u,v) < distance[v]. What does this indicate?

medium

A. The graph contains a negative weight cycle reachable from the source

B. The algorithm has completed successfully with correct distances

C. There is a disconnected vertex in the graph

D. The graph is undirected

Solution

1. Step 1: Understand the relaxation check after iterations

   After |V|-1 relaxations, no edge should improve distances if no negative cycles exist.

2. Step 2: Interpret the condition

   If an edge can still relax a distance, it means a negative weight cycle exists reachable from the source.

3. Final Answer:

   The graph contains a negative weight cycle reachable from the source -> Option A

4. Quick Check:

   Extra relaxation means negative cycle = C [OK]

Hint: Extra relaxation after |V|-1 means negative cycle [OK]

Common Mistakes:

• Thinking algorithm finished correctly despite extra relaxation
• Confusing negative cycle with disconnected vertices
• Assuming graph type (directed/undirected) affects this check

5. Given a graph with vertices V = {S, A, B, C} and edges with weights:
S->A (1), A->B (-1), B->C (-1), C->A (-1)
What will Bellman-Ford detect when run from source S?

hard

A. It will find shortest paths without issues

B. It will report no path to vertex C

C. It will detect a negative weight cycle involving vertices A, B, and C

D. It will fail due to disconnected graph

Solution

1. Step 1: Analyze the cycle formed by A, B, and C

   The edges A->B (-1), B->C (-1), and C->A (-1) form a cycle with total weight -3, which is negative.

2. Step 2: Understand Bellman-Ford behavior on negative cycles

   Bellman-Ford detects negative weight cycles reachable from the source, which prevents shortest path calculation.

3. Final Answer:

   It will detect a negative weight cycle involving vertices A, B, and C -> Option C

4. Quick Check:

   Negative cycle A-B-C with sum -3 detected = B [OK]

Hint: Check cycles' total weight; negative sum means cycle detected [OK]

Common Mistakes:

• Assuming shortest paths exist despite negative cycle
• Ignoring the cycle formed by A, B, and C
• Thinking graph is disconnected when it is not