kotlin coding test course, Floyd-Warshall

Introduction to 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 suitable for calculating the shortest distance for all pairs of a given graph,
and it works even in the presence of negative weights.
Its complexity is O(V^3), where V represents the number of vertices.
The Floyd-Warshall Algorithm utilizes dynamic programming techniques to compute the shortest paths,
incrementally building up the optimal solution.

Problem Description

Given the paths and distances between certain cities,
we will solve the problem of finding the shortest distance between all cities.
This can be very useful for finding optimal routes in heavily trafficked cities.

Problem

There are N cities, and given the distances between the cities,
write a program to output the shortest distance between all cities.
An example input is as follows:

3
0 4 2
float(inf) 0 5
float(inf) float(inf) 0
        

An example output is as follows:

0 4 2
float(inf) 0 5
float(inf) float(inf) 0
        

Solution Process

1. Input Processing

We process the input to solve the problem.
The first line gives the number of cities N, and the following N lines provide the distance information between each city.
‘float(inf)’ indicates there is no path between the two cities.

2. Initial Matrix Creation

Based on the given distance information, we create a 2D array to form the initial matrix.
This matrix contains distance information from city A to city B,
with initial values set to the given distances, and ‘float(inf)’ for cases where there is no path.

3. Applying the Floyd-Warshall Algorithm

The next step is to apply the Floyd-Warshall Algorithm.
The algorithm considers each city K as an intermediate vertex,
determining whether the path from city I to J is shorter by going through city K (i.e.,
if distance[I][J] > distance[I][K] + distance[K][J]),
and updates to the shorter path accordingly.

4. Outputting the Result

We output the shortest distance matrix for all cities.
The result is formatted to distinguish between each city’s shortest distances and ‘float(inf)’.

5. Kotlin Implementation

fun floydWarshall(graph: Array) {
    val n = graph.size
    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (graph[i][j] > graph[i][k] + graph[k][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j]
                }
            }
        }
    }
}

// Main function to execute the program
fun main() {
    val n = readLine()!!.toInt()
    val graph = Array(n) { IntArray(n) { Int.MAX_VALUE } }
    
    // Initialize the graph with input
    for (i in 0 until n) {
        val distances = readLine()!!.split(" ").map { it.toInt() }
        for (j in 0 until n) {
            graph[i][j] = distances[j]
        }
        graph[i][i] = 0 // Distance from a city to itself is always 0
    }
    
    floydWarshall(graph)
    
    // Output the final distance matrix
    for (i in 0 until n) {
        for (j in 0 until n) {
            if (graph[i][j] == Int.MAX_VALUE) {
                print("float(inf) ")
            } else {
                print("${graph[i][j]} ")
            }
        }
        println()
    }
}