Hello! In this lecture, we will learn about the Floyd-Warshall Algorithm, 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.
Problem Description
Here is a problem that utilizes the Floyd-Warshall Algorithm.
Problem: Given N cities and road information between the cities, find the shortest paths between all cities. Each city is numbered from 1 to N, and roads are connected bidirectionally. Road information is provided in the following format: N M x y z Where 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. The distance to oneself (e.g., from city 1 to city 1) is always set to 0. If there are multiple direct roads between two cities, only the road information with the smallest distance is considered. Input Example: 4 7 1 2 4 1 3 2 2 3 5 2 4 10 3 4 3 1 4 8 3 1 3 Output Example: 0 2 3 5 2 0 5 3 3 5 0 3 5 3 3 0
Problem Solving Process
Now, let’s implement the Floyd-Warshall Algorithm to solve this problem. The following explains the algorithm step by step.
1. Set Up Data Structure
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 dist[N + 1][N + 1]. All elements of the array are initialized to infinity (Integer.MAX_VALUE). However, the distance from each city to itself is set to 0.
int[][] dist = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
dist[i][i] = 0;
}2. Initialize Distance Array with Road Information
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.
for (int i = 0; i < M; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
dist[x][y] = Math.min(dist[x][y], z);
dist[y][x] = Math.min(dist[y][x], z);
}3. Implement the Floyd-Warshall Algorithm
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.
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}4. Output the Result
Finally, we output the shortest paths between all cities. The distances from city 1 to city N are printed in order.
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}Complete Code
Now, let’s integrate all the above steps into a single Java program. Below is the complete Java code to solve the problem.
import java.util.Arrays;
import java.util.Scanner;
public class FloydWarshall {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // Number of cities
int M = sc.nextInt(); // Number of roads
int[][] dist = new int[N + 1][N + 1];
// Initialization
for (int i = 1; i <= N; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
dist[i][i] = 0; // Distance to itself is 0
}
// Input road information
for (int i = 0; i < M; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
int z = sc.nextInt();
dist[x][y] = Math.min(dist[x][y], z);
dist[y][x] = Math.min(dist[y][x], z);
}
// Floyd-Warshall Algorithm
for (int k = 1; k <= N; k++) {
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Output results
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print("INF ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
}
}Summary
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.
O(N^3), so for a large number of vertices in a graph, it may be better to consider other shortest path algorithms (e.g., Dijkstra’s Algorithm).
We will continue to introduce various algorithms in the Allelujah coding test course. Thank you!