//using System;
//using System.Collections.Generic;
//using System.Linq;
//using System.Text;
//using System.Threading.Tasks;

//namespace lab10_LFT
//{
//    class Program
//    {
//        public static void Main(string[] args)
//        {
//            var vertices = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
//            var edges = new[]{Tuple.Create(1,2), Tuple.Create(1,3),
//                Tuple.Create(2,4), Tuple.Create(3,5), Tuple.Create(3,6),
//                Tuple.Create(4,7), Tuple.Create(5,7), Tuple.Create(5,8),
//                Tuple.Create(5,6), Tuple.Create(8,9), Tuple.Create(9,10)};

//            var graph = new Graph<int>(vertices, edges);
//            var algorithms = new Algorithms();

//            Console.WriteLine(string.Join(", ", algorithms.DFS(graph, 1)));
//// 1, 3, 6, 5, 8, 9, 10, 7, 4, 2
//        }
//    }
//}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Data;
namespace ConsoleApplication1
{
    class Program
    {
        public class Neighbor
        {
            public Node node { get; set; }
            public int distance { get; set; }
        }
        public class Node
        {

            public string name { get; set; }
            public Dictionary<string, List<string>> distanceDict { get; set; }
            public Boolean visited { get; set; }
            public List<Neighbor> neighbors { get; set; }
        }
        //A connected to B
        //B connected to A, C , D
        //C connected to B, D
        //D connected to B, C , E
        //E connected to D.
        static List<Node> graph = new List<Node>() {
            new Node {name = "A", distanceDict = new Dictionary<string,List<string>>(){
                {"B",new List<string>(){"B"}}, {"C",new List<string>(){"C"}}, {"D",new List<string>(){"D"} } },
                visited = false},
            new Node {name = "B", distanceDict = new Dictionary<string,List<string>>(){
                {"A",new List<string>(){"A"}}, {"C",new List<string>(){"C"}}, {"E",new List<string>(){"E"}}},
                visited = false},
            new Node {name = "C", distanceDict = new Dictionary<string,List<string>>(){
                 {"A",new List<string>(){"A"}}, {"B",new List<string>(){"B"}}, {"D",new List<string>(){"D"}}},
                visited = false},
            new Node {name = "D", distanceDict = new Dictionary<string,List<string>>(){
                {"A",new List<string>(){"A"}}, {"C",new List<string>(){"C"}}, {"E",new List<string>(){"E"}}},
                visited = false},
            new Node {name = "E", distanceDict = new Dictionary<string,List<string>>(){
                {"B",new List<string>(){"B"}}, {"D",new List<string>(){"D"}}},
                visited = false}
        };

        static List<Node> graph2 = new List<Node>() {
            new Node {name = "1", distanceDict = new Dictionary<string,List<string>>(){
                {"2",new List<string>(){"2"}} },
                visited = false},
            new Node {name = "2", distanceDict = new Dictionary<string,List<string>>(){
                {"4",new List<string>(){"4"}}},
                visited = false},
            new Node {name = "3", distanceDict = new Dictionary<string,List<string>>(){
                 {"1",new List<string>(){"1"}}, {"2",new List<string>(){"2"}}, {"4",new List<string>(){"4"}}},
                visited = false},
            new Node {name = "4", distanceDict = new Dictionary<string,List<string>>(){
                {"3",new List<string>(){"3"}} },
                visited = false}

        };
        static void Main(string[] args)
        {
            //initialize neighbors using predefined dixtionary
            foreach (Node node in graph)
            {
                node.neighbors = new List<Neighbor>();
                foreach (KeyValuePair<string, List<string>> neighbor in node.distanceDict)
                {
                    Neighbor newNeightbor = new Neighbor();
                    foreach (Node graphNode in graph)
                    {
                        if (graphNode.name == neighbor.Key)
                        {
                            newNeightbor.node = graphNode;
                            newNeightbor.distance = neighbor.Value.Count;
                            node.neighbors.Add(newNeightbor);
                            break;
                        }
                    }
                }
            }
            TransverNode(graph[0]);
            foreach (Node node in graph)
            {
                Console.WriteLine("Node : {0}", node.name);
                foreach (string key in node.distanceDict.Keys.OrderBy(x => x))
                {
                    Console.WriteLine(" Path to node {0} is {1}", key, string.Join(",", node.distanceDict[key].ToArray()));
                }
            }

            Console.WriteLine("\n\n\n\n");

            //initialize neighbors using predefined dixtionary
            foreach (Node node in graph2)
            {
                node.neighbors = new List<Neighbor>();
                foreach (KeyValuePair<string, List<string>> neighbor in node.distanceDict)
                {
                    Neighbor newNeightbor = new Neighbor();
                    foreach (Node graphNode in graph2)
                    {
                        if (graphNode.name == neighbor.Key)
                        {
                            newNeightbor.node = graphNode;
                            newNeightbor.distance = neighbor.Value.Count;
                            node.neighbors.Add(newNeightbor);
                            break;
                        }
                    }
                }
            }
            TransverNode(graph2[0]);
            foreach (Node node in graph2)
            {
                Console.WriteLine("Node : {0}", node.name);
                foreach (string key in node.distanceDict.Keys.OrderBy(x => x))
                {
                    Console.WriteLine(" Path to node {0} is {1}", key, string.Join(",", node.distanceDict[key].ToArray()));
                }
            }
        }
        static void TransverNode(Node node)
        {
            if (!node.visited)
            {
                node.visited = true;
                foreach (Neighbor neighbor in node.neighbors)
                {
                    TransverNode(neighbor.node);
                    string neighborName = neighbor.node.name;
                    int neighborDistance = neighbor.distance;
                    //compair neibors dictionary with current dictionary
                    //update current dictionary as required
                    foreach (string key in neighbor.node.distanceDict.Keys)
                    {
                        if (key != node.name)
                        {
                            int neighborKeyDistance = neighbor.node.distanceDict[key].Count;
                            if (node.distanceDict.ContainsKey(key))
                            {
                                int currentDistance = node.distanceDict[key].Count;
                                if (neighborKeyDistance + neighborDistance < currentDistance)
                                {
                                    List<string> nodeList = new List<string>();
                                    nodeList.AddRange(neighbor.node.distanceDict[key].ToArray());
                                    nodeList.Insert(0, neighbor.node.name);
                                    node.distanceDict[key] = nodeList;
                                }
                            }
                            else
                            {
                                List<string> nodeList = new List<string>();
                                nodeList.AddRange(neighbor.node.distanceDict[key].ToArray());
                                nodeList.Insert(0, neighbor.node.name);
                                node.distanceDict.Add(key, nodeList);
                            }
                        }
                    }
                }
            }
        }
    }
}