C# Coding Test Course, Finding the K-th Shortest Path

Problem Description

This is a problem of finding the K-th shortest path between two given vertices in a graph. Common shortest path algorithms (such as Dijkstra’s algorithm, Bellman-Ford algorithm, etc.) find only one shortest path, but in this problem, we need to find the K-th shortest path between the given two vertices.

Input Format:

The graph consists of vertices and edges, where each edge has a starting vertex, an ending vertex, and a weight.
The number of vertices in the graph is N, the number of edges is M, and K is the rank of the shortest path to find.

Output Format:

Print the length of the K-th shortest path. If the K-th shortest path does not exist, print -1.

Example

Problem Analysis

The algorithm used to solve this problem is a graph search utilizing a priority queue. It employs a modified approach to traditional shortest path algorithms to find the K-th shortest path. In particular, it explores the necessary paths using a combination of Dijkstra’s algorithm and a priority queue.

The process to solve the problem is as follows:

Receive the graph data and construct it in the form of an adjacency list.
Create a priority queue and start from the source vertex.
Explore paths using the priority queue and count the K-th shortest path.
Once the K-th shortest path is found, output its length.

C# Code Implementation

Below is the code implementing the above process in C#.

        
        using System;
        using System.Collections.Generic;

        class Program
        {
            static void Main(string[] args)
            {
                // Input
                var line = Console.ReadLine().Split();
                int N = int.Parse(line[0]); // Number of vertices
                int M = int.Parse(line[1]); // Number of edges
                int K = int.Parse(line[2]); // K-th shortest path

                // Initialize the graph
                var graph = new List<(int to, int cost)>[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    graph[i] = new List<(int, int)>();
                }

                // Input edge information
                for (int i = 0; i < M; i++)
                {
                    line = Console.ReadLine().Split();
                    int a = int.Parse(line[0]);
                    int b = int.Parse(line[1]);
                    int cost = int.Parse(line[2]);
                    graph[a].Add((b, cost));
                }

                // Find the K-th shortest path
                var result = FindKthShortestPath(graph, N, K);
                Console.WriteLine(result);
            }

            static int FindKthShortestPath(List<(int to, int cost)>[] graph, int N, int K)
            {
                var pq = new SortedSet<(int cost, int node, int count)>();
                pq.Add((0, 1, 0)); // (cost, node, count)

                // List for the K-th shortest path
                var paths = new List[N + 1];
                for (int i = 0; i <= N; i++)
                {
                    paths[i] = new List();
                }

                while (pq.Count > 0)
                {
                    var (cost, node, count) = pq.Min;
                    pq.Remove(pq.Min);

                    paths[node].Add(cost);

                    // If the K-th shortest path is found, return
                    if (count == K - 1)
                    {
                        return cost;
                    }

                    // Explore edges
                    foreach (var edge in graph[node])
                    {
                        pq.Add((cost + edge.cost, edge.to, count + 1));
                    }
                }

                return -1; // If the K-th shortest path does not exist
            }
        }

Time Complexity Analysis

The time complexity of this algorithm is O((M + N) log N). The reasons are:

Adding and removing nodes from the priority queue takes log N time.
As it explores all edges and nodes, it performs O(M + N) iterations, which corresponds to the overall size of the graph.

Conclusion

In this lecture, we implemented code based on the basic concept of graph search to solve the problem of finding the K-th shortest path. By learning how to find the K-th shortest path through a modified approach to shortest path methods, I hope to foster strategic thinking in various algorithmic problems.

In the next lecture, we will cover more complex graph search problems. If you have any questions or feedback, please leave a comment!