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

Need a 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

Need a 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

Need a 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

Need a hint?

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