C# Coding Test Course, Finding the Shortest Path

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.

Problem Description

Here is an example of the “Shortest Path” problem:

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.

Input Format

First line: Number of houses N (1 ≤ N ≤ 1000)
Second line: Number of edges M (1 ≤ M ≤ 10000)
From the third line to the M + 2nd line: Edge information (starting house, ending house, travel time)
Last line: Numbers of House A and House B

Output Format

Print the travel time of the fastest route. If it is not possible to go from House A to House B, print -1.

Solution

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.

Dijkstra’s Algorithm

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:

Initialize the shortest distance from the starting node to 0 and set the distances to all other nodes to infinity.
Use a priority queue to select the node with the shortest distance from the current node.
Update the distance information of the adjacent nodes based on the selected node.
Repeat this process until the shortest distance for all nodes is calculated.

Code Implementation

Now, let’s implement Dijkstra’s algorithm in C#. Below is the code that finds the shortest path using the algorithm:

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int M = int.Parse(Console.ReadLine());

        // Initialize graph
        List>[] graph = new List>[N + 1];
        for (int i = 1; i <= N; i++)
        {
            graph[i] = new List>();
        }

        // Input edges
        for (int i = 0; i < M; i++)
        {
            var line = Console.ReadLine().Split();
            int u = int.Parse(line[0]);
            int v = int.Parse(line[1]);
            int w = int.Parse(line[2]);
            graph[u].Add(new Tuple(v, w));
            graph[v].Add(new Tuple(u, w)); // Bidirectional edge
        }

        var lastLine = Console.ReadLine().Split();
        int start = int.Parse(lastLine[0]);
        int end = int.Parse(lastLine[1]);

        // Find shortest path
        var result = Dijkstra(graph, N, start, end);
        Console.WriteLine(result);
    }

    static int Dijkstra(List>[] graph, int N, int start, int end)
    {
        int[] distances = new int[N + 1];
        bool[] visited = new bool[N + 1];
        int INF = int.MaxValue;

        // Initialize distances to INF
        for (int i = 1; i <= N; i++)
        {
            distances[i] = INF;
        }
        distances[start] = 0;

        // Priority queue
        SortedSet> pq = new SortedSet>();
        pq.Add(new Tuple(0, start));

        while (pq.Count > 0)
        {
            var current = pq.Min;
            pq.Remove(current);

            int currDist = current.Item1;
            int currNode = current.Item2;

            if (visited[currNode])
            {
                continue;
            }
            visited[currNode] = true;

            foreach (var neighbor in graph[currNode])
            {
                int nextNode = neighbor.Item1;
                int weight = neighbor.Item2;

                if (currDist + weight < distances[nextNode])
                {
                    distances[nextNode] = currDist + weight;
                    pq.Add(new Tuple(distances[nextNode], nextNode));
                }
            }
        }

        return distances[end] == INF ? -1 : distances[end];
    }
}

Code Explanation

The above code is an implementation of Dijkstra’s algorithm for finding the shortest path:

Graph Initialization: Input the number of houses N and the number of edges M, and represent the graph as a list.
Input Edges: Input each edge’s information and add it to the graph. Here, it is treated as a bidirectional edge.
Dijkstra Function: 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.

Conclusion

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.