Floyd-Warshall algorithm in Data Structures Theory - Mini Project: Build & Apply

Floyd-Warshall Algorithm

📖 Scenario: You are working with a network of cities connected by roads. You want to find the shortest travel distance between every pair of cities.

🎯 Goal: Build a step-by-step Floyd-Warshall algorithm to find the shortest paths between all pairs of cities in a given network.

📋 What You'll Learn

Create a distance matrix representing direct road distances between cities

Set up the number of cities as a configuration variable

Implement the Floyd-Warshall triple nested loop to update shortest distances

Complete the matrix to show shortest distances between all city pairs

💡 Why This Matters

🌍 Real World

Finding shortest routes between multiple locations is important in GPS navigation, delivery planning, and network routing.

💼 Career

Understanding Floyd-Warshall helps in roles involving algorithms, data analysis, and optimization in software development and logistics.

1

Create the initial distance matrix

Create a 4x4 matrix called dist representing distances between 4 cities. Use these exact values: 0 for distance from a city to itself, 5 from city 0 to 1, 10 from city 0 to 3, 3 from city 1 to 2, 1 from city 2 to 3, and 9999 for no direct road between cities.

Data Structures Theory

# Create the distance matrix 'dist' with the exact values
# Your code here

Need a hint?

Use a list of lists to represent the matrix. Use 9999 to represent no direct road.

2

Set the number of cities

Create a variable called n and set it to 4, representing the number of cities.

Data Structures Theory

dist = [
    [0, 5, 9999, 10],
    [9999, 0, 3, 9999],
    [9999, 9999, 0, 1],
    [9999, 9999, 9999, 0]
]
# Create variable 'n' and set it to 4
# Your code here

Need a hint?

Just assign the number 4 to the variable n.

3

Implement the Floyd-Warshall core logic

Use three nested for loops with variables k, i, and j each ranging from 0 to n (exclusive). Inside the innermost loop, update dist[i][j] to the smaller value between dist[i][j] and dist[i][k] + dist[k][j].

Data Structures Theory

dist = [
    [0, 5, 9999, 10],
    [9999, 0, 3, 9999],
    [9999, 9999, 0, 1],
    [9999, 9999, 9999, 0]
]
n = 4
# Use nested loops with k, i, j to update dist with shortest paths
# Your code here

Need a hint?

Remember to check if going through city k gives a shorter path from i to j.

4

Complete the shortest path matrix

Add a comment line # dist now contains shortest distances between all city pairs to indicate completion.

Data Structures Theory

dist = [
    [0, 5, 9999, 10],
    [9999, 0, 3, 9999],
    [9999, 9999, 0, 1],
    [9999, 9999, 9999, 0]
]
n = 4
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
# Add a comment to show completion
# Your code here

Need a hint?

This comment shows that the algorithm has finished updating the matrix.