using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        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();

​

        var startVertex = 5;

        var destinationVertex = 9;

        var shortestPath = algorithms.ShortestPathFunction(graph, startVertex);

        Console.WriteLine("shortest path to " + destinationVertex + " from start point " + startVertex + " => " +

                          string.Join(", ", shortestPath(destinationVertex)));

        Console.Write("Enter new start point       | u= ");

        int u = Int32.Parse(Console.ReadLine());

        Console.Write("Enter new destination point | v= ");

        int v = Int32.Parse(Console.ReadLine());

        var newShortestPath = algorithms.ShortestPathFunction(graph, u);

        Console.WriteLine("from start " + 

                          u + " to destination " + v + " => " +

                          string.Join(", ", newShortestPath(v)));

        // Vertex = Връх

        // Edge   = Ребро

    }

}

​

​

public class Graph<T> {

    public Graph() {}

    public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T,T>> edges) {

        foreach(var vertex in vertices)

            AddVertex(vertex);

​

        foreach(var edge in edges)

            AddEdge(edge);

    }

​

    public Dictionary<T, HashSet<T>> AdjacencyList = new Dictionary<T, HashSet<T>>();

​

    public void AddVertex(T vertex) {

        AdjacencyList[vertex] = new HashSet<T>();

    }

​

    public void AddEdge(Tuple<T,T> edge) {

        if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2)) {

            AdjacencyList[edge.Item1].Add(edge.Item2);

            AdjacencyList[edge.Item2].Add(edge.Item1);

        }

    }

}

​

public class Algorithms {

    public Func<T, IEnumerable<T>> ShortestPathFunction<T>(Graph<T> graph, T start) {

        var previous = new Dictionary<T, T>();

​

        var queue = new Queue<T>();

        queue.Enqueue(start);

​

        while (queue.Count > 0) {

            var vertex = queue.Dequeue();

            foreach(var neighbor in graph.AdjacencyList[vertex]) {

                if (previous.ContainsKey(neighbor))

                    continue;

​

                previous[neighbor] = vertex;

                queue.Enqueue(neighbor);

            }

        }

​

        Func<T, IEnumerable<T>> shortestPath = v => {

            var path = new List<T>{};

​

            var current = v;

            while (!current.Equals(start)) {

                path.Add(current);

                current = previous[current];

            };

​

            path.Add(start);

            path.Reverse();

​

            return path;

        };

​

        return shortestPath;

    }

}