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

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

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

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

Hint

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

Practice

1. What is the main purpose of the Floyd-Warshall algorithm in graph theory?

easy

A. To perform depth-first search

B. To find the minimum spanning tree

C. To detect cycles in a graph

D. To find shortest paths between all pairs of vertices

Solution

1. Step 1: Understand the algorithm's goal

   The Floyd-Warshall algorithm is designed to find the shortest paths between every pair of vertices in a graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices, cycle detection finds cycles, and DFS explores nodes, none of which match Floyd-Warshall's purpose.

3. Final Answer:

   To find shortest paths between all pairs of vertices -> Option D

4. Quick Check:

   Floyd-Warshall = All pairs shortest paths [OK]

Hint: Remember: Floyd-Warshall finds shortest paths between all pairs [OK]

Common Mistakes:

• Confusing it with minimum spanning tree algorithms
• Thinking it finds shortest path from one source only
• Mixing it up with cycle detection methods

2. Which of the following correctly represents the core update step in the Floyd-Warshall algorithm for vertices i, j, and k?

easy

A. dist[i][j] = dist[i][k] * dist[k][j]

B. dist[i][j] = max(dist[i][j], dist[i][k] + dist[k][j])

C. dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

D. dist[i][j] = dist[i][j] + dist[k][k]

Solution

1. Step 1: Recall the update formula

   The Floyd-Warshall algorithm updates the shortest distance between i and j by checking if going through k is shorter.

2. Step 2: Identify the correct mathematical operation

   The update uses the minimum of the current distance and the sum of distances through k, which matches dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).

3. Final Answer:

   dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) -> Option C

4. Quick Check:

   Update step uses min sum of paths [OK]

Hint: Update distances using minimum sum through intermediate vertex [OK]

Common Mistakes:

• Using max instead of min
• Multiplying distances instead of adding
• Adding distances incorrectly without min

3. Given the following distance matrix for a graph with vertices 0, 1, 2:

dist = [[0, 3, 999],
        [2, 0, 5],
        [999, 1, 0]]

After running one iteration of Floyd-Warshall with intermediate vertex k=1, what is the updated distance from vertex 0 to vertex 2?

medium

A. 8

B. 5

C. 999

D. 3

Solution

1. Step 1: Identify current distances

   dist[0][2] = 999 (no direct path), dist[0][1] = 3, dist[1][2] = 5.

2. Step 2: Calculate new distance via vertex 1

   New distance = dist[0][1] + dist[1][2] = 3 + 5 = 8, which is less than 999, so update dist[0][2] to 8.

3. Final Answer:

   8 -> Option A

4. Quick Check:

   Updated dist[0][2] = 3 + 5 = 8 [OK]

Hint: Add distances through k and compare with current [OK]

Common Mistakes:

• Not updating because original was 999
• Using dist[0][2] directly without checking intermediate
• Mixing vertex indices

4. Consider this incorrect Floyd-Warshall update step:

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j] > dist[i][k] + dist[j][k]:
                dist[i][j] = dist[i][k] + dist[j][k]

What is the main error in this code?

medium

A. The condition uses dist[j][k] instead of dist[k][j]

B. The loops should be reversed in order

C. The update should use max instead of min

D. The code misses initialization of dist matrix

Solution

1. Step 1: Analyze the update condition

   The code compares dist[i][j] with dist[i][k] + dist[j][k], but the second term should be dist[k][j] to represent path i->k->j.

2. Step 2: Identify the correct indexing

   Using dist[j][k] reverses the direction and gives wrong path length, causing incorrect updates.

3. Final Answer:

   The condition uses dist[j][k] instead of dist[k][j] -> Option A

4. Quick Check:

   Correct indexing is dist[k][j] in update [OK]

Hint: Check order of indices in sum: dist[i][k] + dist[k][j] [OK]

Common Mistakes:

• Swapping indices in distance matrix
• Changing loop order unnecessarily
• Confusing min with max in update

5. You have a graph with 4 vertices and the following edges with weights:

(0 -> 1) = 4
(0 -> 2) = 11
(1 -> 2) = -3
(2 -> 3) = 2
(3 -> 1) = 1

Using Floyd-Warshall, what is the shortest distance from vertex 0 to vertex 3 after all iterations?

hard

A. 9

B. 3

C. 6

D. 8

Solution

1. Step 1: Identify possible paths from 0 to 3

   Paths include:
   - 0->1->2->3
   - 0->2->3 directly

2. Step 2: Calculate path distances

   0->1 = 4
   1->2 = -3
   2->3 = 2
   Sum for 0->1->2->3 = 4 + (-3) + 2 = 3
   0->2 = 11
   0->2->3 = 11 + 2 = 13
   Also check 0->1->2->3->1->2->3 cycles but no negative cycle exists.

3. Step 3: Check if going through 3->1->2 improves path

   3->1 = 1, 1->2 = -3, so cycle 1->2->3->1 has total weight 0, no negative cycle.

4. Step 4: Final shortest distance

   Shortest distance from 0 to 3 is 3.

5. Final Answer:

   3 -> Option B

6. Quick Check:

   Shortest distance from 0 to 3 = 4 + (-3) + 2 = 3 [OK]

Hint: Sum edge weights along shortest path carefully [OK]

Common Mistakes:

• Ignoring negative edge weights
• Assuming direct path is shortest
• Not considering cycles properly