Date: October 1, 2023
Introduction
Algorithm problems are one of the important elements in coding tests, especially graph algorithms are used effectively in many situations.
In this article, we will solve a problem using the Floyd-Warshall algorithm.
The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices and mainly uses dynamic programming techniques.
Problem Description
Problem: Finding the Shortest Path
All campuses of your university are represented as vertices, and the roads connecting the campuses are represented as edges.
Calculate the distance of the shortest path from campus A to campus B. Follow the input format below.
Input:
- First line: Total number of campuses N (1 ≤ N ≤ 100)
- Second line: Number of roads M (1 ≤ M ≤ 10000)
- The next M lines: Information about each road in the form (A, B, C), meaning the length of the road from A to B is C.
Output:
- Print the distance matrix of the shortest paths between campuses.
Algorithm Overview
The Floyd-Warshall algorithm is based on the following fundamental principle.
For every pair of vertices (i, j), it compares the distance from i to j through k with the direct path distance and updates the shortest path.
D[i][j] = min(D[i][j], D[i][k] + D[k][j])
This algorithm has a time complexity of O(N^3) and can efficiently compute the shortest paths between all pairs of vertices.
Problem Solving Process
Step 1: Input Handling
To handle input, initialize the array and receive road information.
After initializing the distances to infinity, set the distances between directly connected campuses.
This creates the initial distance matrix D.
Step 2: Implementing the Floyd-Warshall Algorithm
Update the minimum distances between each pair of campuses through three nested loops.
In each iteration, check if there is a shorter path via k, and if so, update the distance matrix.
Step 3: Output the Result
Print the updated distance matrix. Remaining infinite distances indicate unreachable campuses.
C# Code Implementation
using System;
using System.Linq;
class Program
{
const int INF = 987654321; // Define infinity value
static void Main(string[] args)
{
// Input handling
int N = int.Parse(Console.ReadLine());
int M = int.Parse(Console.ReadLine());
int[,] D = new int[N + 1, N + 1];
// Initialize distance array
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (i == j) D[i, j] = 0;
else D[i, j] = INF; // Initialize to infinity
}
}
// Input road information into distance array
for (int i = 0; i < M; i++)
{
var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int A = input[0], B = input[1], C = input[2];
D[A, B] = Math.Min(D[A, B], C); // Set to minimum value as there could be multiple roads
}
// Floyd-Warshall algorithm
for (int k = 1; k <= N; k++)
{
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
D[i, j] = Math.Min(D[i, j], D[i, k] + D[k, j]);
}
}
}
// Output results
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (D[i, j] == INF) Console.Write("INF ");
else Console.Write(D[i, j] + " ");
}
Console.WriteLine();
}
}
}
Conclusion
In this article, we discussed the shortest path problem using the Floyd-Warshall algorithm.
This algorithm is effective in finding the shortest paths between all pairs of vertices and is widely used in real situations.
It is important to understand and apply the Floyd-Warshall algorithm to solve various graph problems.