Hello! In this lecture, we will learn about the Floyd-Warshall Algorithm<\/strong>, which is frequently featured in Java coding tests. The Floyd-Warshall Algorithm is an efficient method for finding the shortest paths from every point to every other point. It is particularly useful when the number of vertices in a graph is small. In this post, we will solve a problem applying the Floyd-Warshall Algorithm and explain the process in detail.<\/p>\n Here is a problem that utilizes the Floyd-Warshall Algorithm.<\/p>\n Now, let’s implement the Floyd-Warshall Algorithm to solve this problem. The following explains the algorithm step by step.<\/p>\n First, we set up a 2D array to store the distance information between all cities. Since there are N cities, the size of the array will be We set the distance information between cities based on the input road information. If multiple roads are provided between two cities, only the shortest distance is saved in the distance array.<\/p>\n The core of the Floyd-Warshall Algorithm is to repeatedly update the shortest distances for all pairs using a triple loop. Below is the implementation code of the Floyd-Warshall Algorithm.<\/p>\n Finally, we output the shortest paths between all cities. The distances from city 1 to city N are printed in order.<\/p>\n Now, let’s integrate all the above steps into a single Java program. Below is the complete Java code to solve the problem.<\/p>\n In this lecture, we solved the problem of finding the shortest paths between cities using the Floyd-Warshall Algorithm. This algorithm can be effectively used to find the shortest paths for all pairs, and it has helped deepen the understanding of the structure and logic of the code. During actual coding tests, it is important to develop efficient problem-solving skills by utilizing such algorithms.<\/p>\nProblem Description<\/h2>\n
\nProblem:<\/strong> Given N cities and road information between the cities, find the shortest paths between all cities. \nEach city is numbered from 1 to N, and roads are connected bidirectionally. \nRoad information is provided in the following format: \n\nN M\nx y z \n\nWhere N is the number of cities, M is the number of roads, x is one city of the road, y is the other city of the road, and z is the distance between the two cities. \nThe distance to oneself (e.g., from city 1 to city 1) is always set to 0. \nIf there are multiple direct roads between two cities, only the road information with the smallest distance is considered.\n\nInput Example:<\/strong>\n4 7\n1 2 4\n1 3 2\n2 3 5\n2 4 10\n3 4 3\n1 4 8\n3 1 3\n\nOutput Example:<\/strong>\n0 2 3 5\n2 0 5 3\n3 5 0 3\n5 3 3 0\n<\/pre>\n
Problem Solving Process<\/h2>\n
1. Set Up Data Structure<\/h3>\n
dist[N + 1][N + 1]<\/code>. All elements of the array are initialized to infinity (Integer.MAX_VALUE<\/code>). However, the distance from each city to itself is set to 0.<\/p>\nint[][] dist = new int[N + 1][N + 1];\n\nfor (int i = 1; i <= N; i++) {\n Arrays.fill(dist[i], Integer.MAX_VALUE);\n dist[i][i] = 0;\n}<\/code><\/pre>\n2. Initialize Distance Array with Road Information<\/h3>\n
for (int i = 0; i < M; i++) {\n int x = sc.nextInt();\n int y = sc.nextInt();\n int z = sc.nextInt();\n dist[x][y] = Math.min(dist[x][y], z);\n dist[y][x] = Math.min(dist[y][x], z);\n}<\/code><\/pre>\n3. Implement the Floyd-Warshall Algorithm<\/h3>\n
for (int k = 1; k <= N; k++) {\n for (int i = 1; i <= N; i++) {\n for (int j = 1; j <= N; j++) {\n if (dist[i][j] > dist[i][k] + dist[k][j]) {\n dist[i][j] = dist[i][k] + dist[k][j];\n }\n }\n }\n}<\/code><\/pre>\n4. Output the Result<\/h3>\n
for (int i = 1; i <= N; i++) {\n for (int j = 1; j <= N; j++) {\n if (dist[i][j] == Integer.MAX_VALUE) {\n System.out.print(\"INF \");\n } else {\n System.out.print(dist[i][j] + \" \");\n }\n }\n System.out.println();\n}<\/code><\/pre>\nComplete Code<\/h2>\n
import java.util.Arrays;\nimport java.util.Scanner;\n\npublic class FloydWarshall {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n int N = sc.nextInt(); \/\/ Number of cities\n int M = sc.nextInt(); \/\/ Number of roads\n\n int[][] dist = new int[N + 1][N + 1];\n\n \/\/ Initialization\n for (int i = 1; i <= N; i++) {\n Arrays.fill(dist[i], Integer.MAX_VALUE);\n dist[i][i] = 0; \/\/ Distance to itself is 0\n }\n\n \/\/ Input road information\n for (int i = 0; i < M; i++) {\n int x = sc.nextInt();\n int y = sc.nextInt();\n int z = sc.nextInt();\n dist[x][y] = Math.min(dist[x][y], z);\n dist[y][x] = Math.min(dist[y][x], z);\n }\n\n \/\/ Floyd-Warshall Algorithm\n for (int k = 1; k <= N; k++) {\n for (int i = 1; i <= N; i++) {\n for (int j = 1; j <= N; j++) {\n if (dist[i][j] > dist[i][k] + dist[k][j]) {\n dist[i][j] = dist[i][k] + dist[k][j];\n }\n }\n }\n }\n\n \/\/ Output results\n for (int i = 1; i <= N; i++) {\n for (int j = 1; j <= N; j++) {\n if (dist[i][j] == Integer.MAX_VALUE) {\n System.out.print(\"INF \");\n } else {\n System.out.print(dist[i][j] + \" \");\n }\n }\n System.out.println();\n }\n }\n}<\/code><\/pre>\nSummary<\/h2>\n