{"id":35182,"date":"2024-11-01T09:36:29","date_gmt":"2024-11-01T09:36:29","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=35182"},"modified":"2024-11-01T11:44:44","modified_gmt":"2024-11-01T11:44:44","slug":"kotlin-coding-test-course-floyd-warshall","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/35182\/","title":{"rendered":"kotlin coding test course, Floyd-Warshall"},"content":{"rendered":"
\n
\n

Algorithm Problem Solving and Theory Explanation<\/p>\n<\/header>\n

\n

Introduction to the Floyd-Warshall Algorithm<\/h2>\n

\n The Floyd-Warshall Algorithm is an algorithm used to find the shortest paths between all pairs of vertices in a graph.
\n This algorithm is suitable for calculating the shortest distance for all pairs of a given graph,
\n and it works even in the presence of negative weights.
\n Its complexity is O(V^3), where V represents the number of vertices.
\n The Floyd-Warshall Algorithm utilizes dynamic programming techniques to compute the shortest paths,
\n incrementally building up the optimal solution.\n <\/p>\n<\/section>\n

\n

Problem Description<\/h2>\n

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

Problem<\/h3>\n

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

\n3\n0 4 2\nfloat(inf) 0 5\nfloat(inf) float(inf) 0\n        <\/pre>\n
\n            An example output is as follows:\n        <\/p>\n
\n0 4 2\nfloat(inf) 0 5\nfloat(inf) float(inf) 0\n        <\/pre>\n<\/section>\n
\n
Solution Process<\/h2>\n
1. Input Processing<\/h3>\n
\n            We process the input to solve the problem.
\n            The first line gives the number of cities N, and the following N lines provide the distance information between each city.
\n            ‘float(inf)’ indicates there is no path between the two cities.\n        <\/p>\n
2. Initial Matrix Creation<\/h3>\n
\n            Based on the given distance information, we create a 2D array to form the initial matrix.
\n            This matrix contains distance information from city A to city B,
\n            with initial values set to the given distances, and ‘float(inf)’ for cases where there is no path.\n        <\/p>\n
3. Applying the Floyd-Warshall Algorithm<\/h3>\n
\n            The next step is to apply the Floyd-Warshall Algorithm.
\n            The algorithm considers each city K as an intermediate vertex,
\n            determining whether the path from city I to J is shorter by going through city K (i.e.,
\n            if distance[I][J] > distance[I][K] + distance[K][J]),
\n            and updates to the shorter path accordingly.\n        <\/p>\n
4. Outputting the Result<\/h3>\n
\n            We output the shortest distance matrix for all cities.
\n            The result is formatted to distinguish between each city’s shortest distances and ‘float(inf)’.\n        <\/p>\n
5. Kotlin Implementation<\/h3>\n
\nfun floydWarshall(graph: Array) {\n    val n = graph.size\n    for (k in 0 until n) {\n        for (i in 0 until n) {\n            for (j in 0 until n) {\n                if (graph[i][j] > graph[i][k] + graph[k][j]) {\n                    graph[i][j] = graph[i][k] + graph[k][j]\n                }\n            }\n        }\n    }\n}\n\n\/\/ Main function to execute the program\nfun main() {\n    val n = readLine()!!.toInt()\n    val graph = Array(n) { IntArray(n) { Int.MAX_VALUE } }\n    \n    \/\/ Initialize the graph with input\n    for (i in 0 until n) {\n        val distances = readLine()!!.split(\" \").map { it.toInt() }\n        for (j in 0 until n) {\n            graph[i][j] = distances[j]\n        }\n        graph[i][i] = 0 \/\/ Distance from a city to itself is always 0\n    }\n    \n    floydWarshall(graph)\n    \n    \/\/ Output the final distance matrix\n    for (i in 0 until n) {\n        for (j in 0 until n) {\n            if (graph[i][j] == Int.MAX_VALUE) {\n                print(\"float(inf) \")\n            } else {\n                print(\"${graph[i][j]} \")\n            }\n        }\n        println()\n    }\n}\n        <\/intarray><\/pre>\n<\/section>\n