{"id":33884,"date":"2024-11-01T09:21:39","date_gmt":"2024-11-01T09:21:39","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33884"},"modified":"2024-11-01T10:55:26","modified_gmt":"2024-11-01T10:55:26","slug":"c-coding-test-course-floyd-warshall","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33884\/","title":{"rendered":"C# Coding Test Course, Floyd-Warshall"},"content":{"rendered":"
\n
\n

Date: October 1, 2023<\/p>\n<\/header>\n

\n

Introduction<\/h2>\n

\n Algorithm problems are one of the important elements in coding tests, especially graph algorithms are used effectively in many situations.
\n In this article, we will solve a problem using the Floyd-Warshall algorithm.
\n The Floyd-Warshall algorithm is used to find the shortest path between all pairs of vertices and mainly uses dynamic programming techniques.\n <\/p>\n<\/section>\n

\n

Problem Description<\/h2>\n

Problem: Finding the Shortest Path<\/h3>\n

\n All campuses of your university are represented as vertices, and the roads connecting the campuses are represented as edges.
\n Calculate the distance of the shortest path from campus A to campus B. Follow the input format below.\n <\/p>\n

\n            Input:\n            - First line: Total number of campuses N (1 \u2264 N \u2264 100)\n            - Second line: Number of roads M (1 \u2264 M \u2264 10000)\n            - 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.\n            \n            Output:\n            - Print the distance matrix of the shortest paths between campuses.\n        <\/pre>\n<\/section>\n
\n
Algorithm Overview<\/h2>\n
\n            The Floyd-Warshall algorithm is based on the following fundamental principle.
\n            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.\n        <\/p>\n
\n            D[i][j] = min(D[i][j], D[i][k] + D[k][j])\n        <\/pre>\n
\n            This algorithm has a time complexity of O(N^3) and can efficiently compute the shortest paths between all pairs of vertices.\n        <\/p>\n<\/section>\n
\n
Problem Solving Process<\/h2>\n
Step 1: Input Handling<\/h3>\n
\n            To handle input, initialize the array and receive road information.
\n            After initializing the distances to infinity, set the distances between directly connected campuses.
\n            This creates the initial distance matrix D.\n        <\/p>\n
Step 2: Implementing the Floyd-Warshall Algorithm<\/h3>\n
\n            Update the minimum distances between each pair of campuses through three nested loops.
\n            In each iteration, check if there is a shorter path via k, and if so, update the distance matrix.\n        <\/p>\n
Step 3: Output the Result<\/h3>\n
\n            Print the updated distance matrix. Remaining infinite distances indicate unreachable campuses.\n        <\/p>\n<\/section>\n
\n
C# Code Implementation<\/h2>\n
\n            \n            using System;\n            using System.Linq;\n\n            class Program\n            {\n                const int INF = 987654321; \/\/ Define infinity value\n\n                static void Main(string[] args)\n                {\n                    \/\/ Input handling\n                    int N = int.Parse(Console.ReadLine());\n                    int M = int.Parse(Console.ReadLine());\n\n                    int[,] D = new int[N + 1, N + 1];\n\n                    \/\/ Initialize distance array\n                    for (int i = 1; i <= N; i++)\n                    {\n                        for (int j = 1; j <= N; j++)\n                        {\n                            if (i == j) D[i, j] = 0;\n                            else D[i, j] = INF; \/\/ Initialize to infinity\n                        }\n                    }\n\n                    \/\/ Input road information into distance array\n                    for (int i = 0; i < M; i++)\n                    {\n                        var input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();\n                        int A = input[0], B = input[1], C = input[2];\n                        D[A, B] = Math.Min(D[A, B], C); \/\/ Set to minimum value as there could be multiple roads\n                    }\n\n                    \/\/ Floyd-Warshall algorithm\n                    for (int k = 1; k <= N; k++)\n                    {\n                        for (int i = 1; i <= N; i++)\n                        {\n                            for (int j = 1; j <= N; j++)\n                            {\n                                D[i, j] = Math.Min(D[i, j], D[i, k] + D[k, j]);\n                            }\n                        }\n                    }\n\n                    \/\/ Output results\n                    for (int i = 1; i <= N; i++)\n                    {\n                        for (int j = 1; j <= N; j++)\n                        {\n                            if (D[i, j] == INF) Console.Write(\"INF \");\n                            else Console.Write(D[i, j] + \" \");\n                        }\n                        Console.WriteLine();\n                    }\n                }\n            }\n            <\/code>\n        <\/pre>\n<\/section>\n
\n
Conclusion<\/h2>\n
\n            In this article, we discussed the shortest path problem using the Floyd-Warshall algorithm.
\n            This algorithm is effective in finding the shortest paths between all pairs of vertices and is widely used in real situations.
\n            It is important to understand and apply the Floyd-Warshall algorithm to solve various graph problems.\n        <\/p>\n<\/section>\n