using System;

using System.Collections.Generic;

using System.Linq;

​

public class Dijkstra

{

    public static Dictionary<string, int> FindShortestDistances(Dictionary<string, Dictionary<string, int>> graph, string start)

    {

        // Initialise distances with infinity for all nodes except the start node

        var distances = graph.Keys.ToDictionary(node => node, node => int.MaxValue);

        distances[start] = 0;

​

        // Priority queue to keep track of the next node to visit

        var priorityQueue = new PriorityQueue<(int, string), int>();

        priorityQueue.Enqueue((0, start), 0);

​

        while (priorityQueue.Count > 0)

        {

            (int currentDistance, string currentNode) = priorityQueue.Dequeue();

​

            // If the current distance is greater than the known distance, skip

            if (currentDistance > distances[currentNode])

            {

                continue;

            }

​

            foreach (var (neighbour, weight) in graph[currentNode])

            {

                int distance = currentDistance + weight;

​

                // If a shorter path is found, update the distance and enqueue the neighbour

                if (distance < distances[neighbour])

                {

                    distances[neighbour] = distance;

                    priorityQueue.Enqueue((distance, neighbour), distance);

                }

            }

        }

​

        return distances;

    }

​

    public static void Main(string[] args)

    {

        // Example graph represented as an adjacency list

        var graph = new Dictionary<string, Dictionary<string, int>>

        {

             { "Ledbury", new Dictionary<string, int> { { "Malvern", 8 }, { "Hereford", 15 }, { "Cheltenham", 22 } } },

             { "Malvern", new Dictionary<string, int> { { "Ledbury", 8 }, { "Worcester", 9 } } },

             { "Worcester", new Dictionary<string, int> { { "Malvern", 9 }, { "Hereford", 27 } } },

             { "Hereford", new Dictionary<string, int> { { "Ledbury", 15 }, { "Worcester", 27 } } }

        };

        string startNode = "Ledbury";

        var shortestDistances = FindShortestDistances(graph, startNode);

​

        Console.WriteLine($"Shortest distances from node {startNode}: {string.Join(", ", shortestDistances.Select(pair => $"{pair.Key}: {pair.Value}"))}");

    }

}