Hello everyone! Today, we will deeply explore how to implement Dijkstra’s algorithm using C# and how to solve algorithmic problems through it. This tutorial will provide a step-by-step explanation of the basic concepts of the algorithm, problem definition, C# code implementation, and optimization methods.<\/p>\n
Dijkstra’s algorithm is a method for finding the shortest path in a graph. It is particularly useful when the weights of all edges are greater than or equal to zero. This algorithm efficiently calculates the shortest path from a specific node to all other nodes.<\/p>\n
The basic principle of Dijkstra’s algorithm is as follows:<\/p>\n
The problem we will solve together is “Finding the Shortest Path.” There is a given graph consisting of nodes and edges, and we need to find the shortest distance from a specific starting node to all other nodes.<\/p>\n
The input for the problem is as follows:<\/p>\n
The output is the shortest distance to each node. Nodes that cannot be reached are marked as “INF”.<\/p>\n
To implement Dijkstra’s algorithm in C#, we can use the following libraries and data structures:<\/p>\n
First, let’s take a look at the complete code to implement Dijkstra’s algorithm in C#.<\/p>\n
\nusing System;\nusing System.Collections.Generic;\n\nclass Program\n{\n static void Main()\n {\n int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n int N = input[0];\n int M = input[1];\n\n List>[] graph = new List>[N + 1];\n for (int i = 0; i <= N; i++)\n graph[i] = new List>();\n\n for (int i = 0; i < M; i++)\n {\n input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);\n graph[input[0]].Add(new Tuple(input[1], input[2]));\n graph[input[1]].Add(new Tuple(input[0], input[2])); \/\/ For undirected graphs\n }\n\n int K = int.Parse(Console.ReadLine());\n int[] distances = Dijkstra(graph, N, K);\n\n for (int i = 1; i <= N; i++)\n {\n Console.WriteLine(distances[i] == int.MaxValue ? \"INF\" : distances[i].ToString());\n }\n }\n\n static int[] Dijkstra(List>[] graph, int N, int start)\n {\n int[] distances = new int[N + 1];\n for (int i = 1; i <= N; i++)\n distances[i] = int.MaxValue;\n distances[start] = 0;\n\n PriorityQueue priorityQueue = new PriorityQueue();\n priorityQueue.Enqueue(start, 0);\n\n while (priorityQueue.Count > 0)\n {\n var current = priorityQueue.Dequeue();\n int currentNode = current.Item1;\n int currentDistance = current.Item2;\n\n if (currentDistance > distances[currentNode]) continue;\n\n foreach (var edge in graph[currentNode])\n {\n int nextNode = edge.Item1;\n int weight = edge.Item2;\n\n if (distances[currentNode] + weight < distances[nextNode])\n {\n distances[nextNode] = distances[currentNode] + weight;\n priorityQueue.Enqueue(nextNode, distances[nextNode]);\n }\n }\n }\n\n return distances;\n }\n}\n<\/int,><\/int,><\/tuple<\/int,><\/int,><\/tuple<\/tuple<\/tuple<\/code><\/pre>\n5. Code Explanation<\/h2>\n
The code above implements Dijkstra’s algorithm. Let\u2019s explain the function of each part in detail.<\/p>\n
5.1. Main Function<\/h3>\n
The main function takes input, constructs the graph, and then calls the Dijkstra function.<\/p>\n
\n- Receives input to determine N and M.<\/li>\n
- Initializes the graph represented as a list for each node.<\/li>\n
- Constructs the graph based on the given edge information.<\/li>\n
- Takes the starting node K as input and calls the Dijkstra function to return the shortest distance array.<\/li>\n
- Outputs the shortest distance for each node. If unreachable, it displays “INF”.<\/li>\n<\/ul>\n
5.2. Dijkstra Function<\/h3>\n
The Dijkstra function contains the core logic of the Dijkstra algorithm.<\/p>\n
\n- Initializes the distance array.<\/li>\n
- Uses a priority queue to store current node information and selects the node with the smallest distance.<\/li>\n
- Performs shortest distance updates for adjacent nodes of the current node.<\/li>\n<\/ul>\n
6. Test Cases<\/h2>\n
Now, let’s create some test cases to verify if Dijkstra’s algorithm works correctly.<\/p>\n
6.1. Test Case 1<\/h3>\nInput:<\/h4>\n\n5 6\n1 2 2\n1 3 3\n2 3 1\n2 4 5\n3 4 2\n3 5 1\n1\n<\/code><\/pre>\nOutput:<\/h4>\n\n0\n2\n3\n5\n4\n<\/code><\/pre>\n6.2. Test Case 2<\/h3>\nInput:<\/h4>\n\n4 4\n1 2 3\n1 3 1\n2 4 1\n3 4 5\n1\n<\/code><\/pre>\nOutput:<\/h4>\n\n0\n3\n1\n4\n<\/code><\/pre>\n7. Summary and Optimization<\/h2>\n
In this tutorial, we implemented Dijkstra’s algorithm using C# and solved the shortest path problem. To improve the efficiency of Dijkstra’s algorithm, we can consider the following optimization methods:<\/p>\n