Swift Coding Test Course, Floyd-Warshall

1. Overview of the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is an algorithm used to find the shortest paths between all pairs of vertices in a graph. This algorithm is based on dynamic programming and updates the shortest paths by considering paths that pass through vertex k at each step. The time complexity of the Floyd-Warshall algorithm is O(V³), where V represents the number of vertices.

1.1. Significance of the Algorithm

The Floyd-Warshall algorithm exhibits excellent efficiency in that it can identify the shortest paths between all pairs of vertices through a single process, not just finding the shortest path from a single starting point.

1.2. Applications

This algorithm is applied in various fields including calculating the shortest paths between all nodes in a network, optimizing road networks, and computing movement paths in games.

2. Working Principle of the Algorithm

The Floyd-Warshall algorithm operates in the following manner:

1. Initialize the shortest paths for all edges of the graph. The distance between two directly connected vertices is set to the weight of the edge, while the remaining pairs are set to infinity.
2. For each vertex k, update the shortest paths for all combinations of vertices i and j as follows: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. Repeat this process for all pairs of vertices.

This algorithm allows us to find the shortest paths when there are paths that pass through vertex k.

3. Example Problem

Problem Description

Here is a problem that can be solved using the Floyd-Warshall algorithm:

Given a directed graph consisting of N vertices and M edges, write a program to find the shortest distance between each pair of vertices. The weights of the edges are given as positive integers, and if there is no edge between two vertices, it should be set to infinity.

Problem Input

The first line contains the number of vertices N (1 ≤ N ≤ 100) and the number of edges M (1 ≤ M ≤ 100,000). The next M lines provide the starting vertex, ending vertex, and weight of each edge. If there are multiple edges between two vertices, only the edge with the smallest weight should be considered.

Problem Output

Output the shortest distance between each pair of vertices. If the shortest distance does not exist, output INF.

Example

Input:

        4 7
        1 2 1
        1 3 3
        2 3 1
        2 4 2
        3 4 1
        4 1 2
        4 2 3
        

Output:

        0 1 2 3
        INF 0 1 2
        INF INF 0 1
        2 1 2 0
        

4. Problem Solving Process

To solve the problem, we will implement the Floyd-Warshall algorithm. Below is the step-by-step process of problem-solving.

4.1. Initial Setup

First, set up the initial distance array using N vertices and M edges. The weights between directly connected vertices are set to the given values, and the distances for unconnected vertices are set to infinity.

4.2. Initialize Distance Array

        var N = 4
        var M = 7
        var dist = [[Int]](repeating: [Int](repeating: Int.max, count: N + 1), count: N + 1)
        
        for i in 1...N {
            dist[i][i] = 0
        }
        

This code initializes the distance array dist to infinity and sets the distance to itself as 0.

4.3. Input Edge Information

        dist[1][2] = 1
        dist[1][3] = 3
        dist[2][3] = 1
        dist[2][4] = 2
        dist[3][4] = 1
        dist[4][1] = 2
        dist[4][2] = 3
        

Now, set the weights between directly connected vertices using the edge information. If there are multiple edges, update it to the minimum weight.

4.4. Apply the Floyd-Warshall Algorithm

        for k in 1...N {
            for i in 1...N {
                for j in 1...N {
                    if dist[i][j] > dist[i][k] + dist[k][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
        

Here, k acts as an intermediate vertex, updating the shortest path from i to j.

4.5. Output Results

        for i in 1...N {
            for j in 1...N {
                if dist[i][j] == Int.max {
                    print("INF", terminator: " ")
                } else {
                    print(dist[i][j], terminator: " ")
                }
            }
            print("")
        }
        

Finally, output the distance array to check the shortest distances between each pair of vertices.

5. Conclusion

In this lecture, we learned the concepts and operating principles of the Floyd-Warshall algorithm and examined the process of solving actual problems. This algorithm is a powerful tool for efficiently finding the shortest paths between all pairs of vertices. It is important to solve various examples to enhance your understanding of the algorithm. You should also practice solving algorithm problems in Swift to improve your skills!