using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Graph shortest path");

        List<KeyValuePair<string, string>> edges = new();

        edges.Add(KeyValuePair.Create<string, string>("w", "x"));

        edges.Add(KeyValuePair.Create<string, string>("x", "y"));

        edges.Add(KeyValuePair.Create<string, string>("z", "y"));

        edges.Add(KeyValuePair.Create<string, string>("z", "v"));

        edges.Add(KeyValuePair.Create<string, string>("w", "v"));

        Dictionary<string, List<string>> graph = GenerateGraphStructure(edges);

        foreach (var node in graph)

        {

            Console.Write($"{node.Key} :");

            foreach (var nbr in node.Value)

            {

                Console.Write($" {nbr} ");

            }

​

            Console.WriteLine();

        }

        Console.WriteLine($"shortest path {ShortestPath(graph, "w", "z")}");

    }

​

    public static int ShortestPath(Dictionary<string, List<string>> graph, string src, string dst)

    {

        if(!graph.ContainsKey(src) || !graph.ContainsKey(dst)) {return -1;}

        //base case     

        if (src.Equals(dst))

        {

            return 0;

        }

​

        int path = 0;

        HashSet<string> visited = new();

        Queue<KeyValuePair<string, int>> bfsQueue = new();

        bfsQueue.Enqueue(KeyValuePair.Create<string, int>(src, 0));

        visited.Add(src);

        while (bfsQueue.Count > 0)

        {

            (string node, path) = bfsQueue.Dequeue();

            Console.WriteLine($"dequeued - {node}");

            if (node.Equals(dst))

            {

                Console.WriteLine($"returning - {node} {path}");

                return path;

            }

            else

            {

                foreach (var nbr in graph[node])

                {

                    if(!visited.Contains(nbr)){

                        visited.Add(nbr);

                        bfsQueue.Enqueue(KeyValuePair.Create<string, int>(nbr, path+1));

                        Console.WriteLine($"{nbr} {path+1}");

                    }

                    else

                    {

                        Console.WriteLine($"visited - {nbr}");

                    }

                }

            }

        }

        return -1;

    }

​

    public static Dictionary<string, List<string>> GenerateGraphStructure(List<KeyValuePair<string, string>> edges)

    {

        Dictionary<string, List<string>> graph = new();

        foreach (var edge in edges)

        {

            if (!graph.ContainsKey(edge.Key))

            {

                graph.Add(edge.Key, new() { edge.Value });

                PopulateEdgeValues(ref graph, edge);

            }

            else

            {

                (graph[edge.Key]).Add(edge.Value);

                PopulateEdgeValues(ref graph, edge);

            }

        }

​

        return graph;

    }

​

    public static void PopulateEdgeValues(ref Dictionary<string, List<string>> graph, KeyValuePair<string, string> edge)

    {

        if (graph.ContainsKey(edge.Value))

        {

            (graph[edge.Value]).Add(edge.Key);

        }

        else

        {

            graph.Add(edge.Value, new() { edge.Key });

        }

    }

}