Floyd-Warshall Algorithm in Kotlin

by

The Floyd-Warshall algorithm (also known as Warshall’s algorithm) is an algorithm used to find the shortest paths in a weighted graph with positive or negative edge weights. The algorithm was developed by Robert Floyd and Stephen Warshall in 1962.

Here’s how the algorithm works:

  1. Initialize a distance matrix dist with the distances between each pair of nodes in the graph. If there is no edge between two nodes, the distance should be set to infinity.
  2. For each node k in the graph, consider it as a potential intermediate node in the paths between all pairs of nodes. Update the distance matrix dist by checking if the path between node i and node j is shorter if we go through node k. If it is, update the distance in dist to the new shorter distance.
  3. After all k nodes have been considered, the dist matrix will contain the shortest path distances between all pairs of nodes.
Kotlin
fun floydWarshall(graph: Array<IntArray>): Array<IntArray> {
    val n = graph.size
    val dist = graph.clone() // Initialize distance matrix
    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (dist[i][k] != Int.MAX_VALUE && dist[k][j] != Int.MAX_VALUE &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
    return dist
}

The floydWarshall function takes a 2D array graph representing the adjacency matrix of the graph. Each element graph[i][j] represents the weight of the edge from node i to node j. If there is no edge between two nodes, the value should be Int.MAX_VALUE.

The function initializes the dist matrix to be a copy of the graph matrix. Then, for each node k in the graph, the function updates the dist matrix by checking if the path between node i and node j is shorter if we go through node k. If it is, the distance in the dist matrix is updated to the new shorter distance.

After all nodes k have been considered, the dist matrix will contain the shortest path distances between all pairs of nodes. The function returns the dist matrix.

Note that the time complexity of the Floyd-Warshall algorithm is O(n^3), where n is the number of nodes in the graph. The space complexity is also O(n^2), since we need to store the dist matrix.

Kotlin
fun floydWarshall(graph: Array<IntArray>): Array<IntArray> {
    val n = graph.size
    val dist = graph.clone() // Initialize distance matrix
    for (k in 0 until n) {
        for (i in 0 until n) {
            for (j in 0 until n) {
                if (dist[i][k] != Int.MAX_VALUE && dist[k][j] != Int.MAX_VALUE &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
    return dist
}
fun main() {
    // Example graph with 4 nodes and 6 edges
    val graph = arrayOf(
        intArrayOf(0, 1, 4, Int.MAX_VALUE),
        intArrayOf(1, 0, 2, 5),
        intArrayOf(4, 2, 0, 1),
        intArrayOf(Int.MAX_VALUE, 5, 1, 0)
    )
    val shortestDistances = floydWarshall(graph) // Find shortest paths
    for (i in 0 until graph.size) {
        for (j in 0 until graph.size) {
            print("${shortestDistances[i][j]}\t")
        }
        println()
    }
}

we define a graph with 4 nodes and 6 edges, represented as an adjacency matrix in the graph array. We then call the floydWarshall function with the graph array as an argument, and store the result in the shortestDistances array.

Finally, we print out the shortestDistances matrix, which contains the shortest path distances between all pairs of nodes in the graph.

This indicates that the shortest path from node 0 to node 1 has a length of 1, the shortest path from node 0 to node 2 has a length of 3, and so on.

Leave a Comment