python coding test course, Floyd-Warshall

Hello! In this tutorial, we will delve deep into the Floyd-Warshall algorithm. This algorithm is very useful for solving the problem of finding the shortest paths between all pairs in a given graph. We will explain this algorithm through examples, and discuss various modifications including optimizations.

What is the Floyd-Warshall Algorithm?

The Floyd-Warshall algorithm is used in graph theory to find the shortest paths between all nodes. This algorithm operates through the following steps:

1. Set the initial distance values for each pair of vertices in the graph.
2. Consider each vertex as a starting vertex and update the shortest distances.
3. Repeatedly update the distance matrix to ultimately find the shortest distances for all pairs.

Problem Description

Now let’s examine the problem. Suppose we are given a graph as follows.

        Nodes: 0, 1, 2
        Edges: 
        0 -> 1 (distance 3)
        0 -> 2 (distance 8)
        1 -> 2 (distance 2)
    

Input

The number of nodes in the graph and the distance information for each edge will be provided. Input is received in the following format:

    3
    0 1 3
    0 2 8
    1 2 2
    

Output

The shortest distance matrix between each pair of nodes will be output.

Algorithm Implementation

Now let’s implement the Floyd-Warshall algorithm in Python. Below is the code for the algorithm:

def floyd_warshall(num_vertices, edges):
    # Initialize distances to infinity
    dist = [[float('inf')] * num_vertices for _ in range(num_vertices)]
    
    # Distance to self is 0
    for i in range(num_vertices):
        dist[i][i] = 0
        
    # Set initial distances based on given edges
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # Set minimum distance if multiple paths exist
    
    # Execute the Floyd-Warshall algorithm
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

# Take input
num_vertices = int(input("Enter the number of nodes: "))
edges = []

for _ in range(int(input("Enter the number of edges: "))):
    u, v, w = map(int, input("Enter the edge (u, v, distance): ").split())
    edges.append((u, v, w))

# Execute the algorithm
shortest_paths = floyd_warshall(num_vertices, edges)

# Output results
for row in shortest_paths:
    print(row)
    

Code Explanation

Now let’s look at the code step by step.

Distance Initialization

We create the distance matrix based on the number of nodes in the graph. Initially, all distances are set to infinity, and the distance to itself is set to 0.

Edge Input Processing

We read the given edge information and set the initial distances between each pair of nodes. If multiple edges exist, we choose the minimum distance.

Main Algorithm Logic

We use three nested loops to compute the shortest paths between all pairs of nodes. This loop uses k as an intermediate vertex to update the shortest path from i to j.

Execution Example

Let’s execute the algorithm as follows:

    Enter the number of nodes: 3
    Enter the number of edges: 3
    Enter the edge (u, v, distance): 0 1 3
    Enter the edge (u, v, distance): 0 2 8
    Enter the edge (u, v, distance): 1 2 2
    

The output when executing the above example would be as follows:

    [0, 3, 5]
    [inf, 0, 2]
    [inf, inf, 0]
    

Conclusion

The Floyd-Warshall algorithm is a very useful algorithm for finding the shortest paths between all pairs. Through this algorithm, we can efficiently find the shortest paths even in complex structures of graphs. It’s important to practice applying this algorithm to solve various problems. In the next coding test, try to solve various problems using this algorithm!