{"id":33852,"date":"2024-11-01T09:21:15","date_gmt":"2024-11-01T09:21:15","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33852"},"modified":"2024-11-01T10:55:49","modified_gmt":"2024-11-01T10:55:49","slug":"c-coding-test-course-finding-the-shortest-path","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33852\/","title":{"rendered":"C# Coding Test Course, Finding the Shortest Path"},"content":{"rendered":"<\/p>\n
In this course, we will solve the “Shortest Path” problem, which is commonly asked in algorithm tests using C#. This topic is very useful for understanding the basic concepts of graph theory and developing algorithmic problem-solving skills. In particular, we will explore how to solve this problem using popular algorithms such as Dijkstra’s algorithm.<\/p>\n
Problem Description<\/h2>\n
Here is an example of the “Shortest Path” problem:<\/p>\n
In a village, there are N houses, and these houses are connected by edges. Each edge represents the time it takes to travel. Now, find the fastest route from House A to House B. The input consists of the number of houses N, the number of edges M, the information of each edge (starting house, ending house, travel time), and finally the numbers of House A and House B.<\/p>\n
Input Format<\/h3>\n
\n
First line: Number of houses N (1 \u2264 N \u2264 1000)<\/li>\n
Second line: Number of edges M (1 \u2264 M \u2264 10000)<\/li>\n
From the third line to the M + 2nd line: Edge information (starting house, ending house, travel time)<\/li>\n
Last line: Numbers of House A and House B<\/li>\n<\/ul>\n
Output Format<\/h3>\n
Print the travel time of the fastest route. If it is not possible to go from House A to House B, print -1.<\/p>\n
Solution<\/h2>\n
To solve this problem, we will use Dijkstra’s algorithm from graph theory. This algorithm is very effective for finding the shortest path in graphs with non-negative weights.<\/p>\n
Dijkstra’s Algorithm<\/h3>\n
Dijkstra’s algorithm is a greedy algorithm that finds the shortest path from the starting node to all other nodes. The main idea of this algorithm is as follows:<\/p>\n
\n
Initialize the shortest distance from the starting node to 0 and set the distances to all other nodes to infinity.<\/li>\n
Use a priority queue to select the node with the shortest distance from the current node.<\/li>\n
Update the distance information of the adjacent nodes based on the selected node.<\/li>\n
Repeat this process until the shortest distance for all nodes is calculated.<\/li>\n<\/ol>\n
Code Implementation<\/h3>\n
Now, let’s implement Dijkstra’s algorithm in C#. Below is the code that finds the shortest path using the algorithm:<\/p>\n
using System;\nusing System.Collections.Generic;\n\nclass Program\n{\n static void Main(string[] args)\n {\n int N = int.Parse(Console.ReadLine());\n int M = int.Parse(Console.ReadLine());\n\n \/\/ Initialize graph\n List>[] graph = new List>[N + 1];\n for (int i = 1; i <= N; i++)\n {\n graph[i] = new List>();\n }\n\n \/\/ Input edges\n for (int i = 0; i < M; i++)\n {\n var line = Console.ReadLine().Split();\n int u = int.Parse(line[0]);\n int v = int.Parse(line[1]);\n int w = int.Parse(line[2]);\n graph[u].Add(new Tuple(v, w));\n graph[v].Add(new Tuple(u, w)); \/\/ Bidirectional edge\n }\n\n var lastLine = Console.ReadLine().Split();\n int start = int.Parse(lastLine[0]);\n int end = int.Parse(lastLine[1]);\n\n \/\/ Find shortest path\n var result = Dijkstra(graph, N, start, end);\n Console.WriteLine(result);\n }\n\n static int Dijkstra(List>[] graph, int N, int start, int end)\n {\n int[] distances = new int[N + 1];\n bool[] visited = new bool[N + 1];\n int INF = int.MaxValue;\n\n \/\/ Initialize distances to INF\n for (int i = 1; i <= N; i++)\n {\n distances[i] = INF;\n }\n distances[start] = 0;\n\n \/\/ Priority queue\n SortedSet> pq = new SortedSet>();\n pq.Add(new Tuple(0, start));\n\n while (pq.Count > 0)\n {\n var current = pq.Min;\n pq.Remove(current);\n\n int currDist = current.Item1;\n int currNode = current.Item2;\n\n if (visited[currNode])\n {\n continue;\n }\n visited[currNode] = true;\n\n foreach (var neighbor in graph[currNode])\n {\n int nextNode = neighbor.Item1;\n int weight = neighbor.Item2;\n\n if (currDist + weight < distances[nextNode])\n {\n distances[nextNode] = currDist + weight;\n pq.Add(new Tuple(distances[nextNode], nextNode));\n }\n }\n }\n\n return distances[end] == INF ? -1 : distances[end];\n }\n}\n<\/int,><\/int,><\/tuple<\/tuple<\/tuple<\/int,><\/int,><\/tuple<\/tuple<\/tuple<\/code><\/pre>\n
Code Explanation<\/h2>\n
The above code is an implementation of Dijkstra’s algorithm for finding the shortest path:<\/p>\n
\n
Graph Initialization:<\/strong> Input the number of houses N and the number of edges M, and represent the graph as a list.<\/li>\n
Input Edges:<\/strong> Input each edge’s information and add it to the graph. Here, it is treated as a bidirectional edge.<\/li>\n
Dijkstra Function:<\/strong> Contains the logic for finding the shortest path. Initializes the distance array and visit array, and uses a priority queue to select the node with the shortest distance.<\/li>\n<\/ul>\n
Conclusion<\/h2>\n
In this course, we solved the shortest path problem using C#. We learned that Dijkstra’s algorithm can effectively find the shortest path in graphs. This technique can be very useful in coding tests and real-world development as well. I encourage you to solidify the basics of this algorithm by solving various problems.<\/p>\n