Практикум16_IV

public class Graph
    {
        private class Node
        {
            List<List<int>> array = new List<List<int>>();
            int countVertex;
            bool[] nov;

            public Node(List<List<int>> tmp, int n)
            {
                array = tmp;
                countVertex = n;
                nov = new bool[countVertex];
            }

            public int Size
            {
                get { return countVertex; }
            }

            public void NovSet()
            {
                for (int i = 0; i < countVertex; i++)
                    nov[i] = false;
            }

            public long[,] Floyd(out int[,] p)
            {
                int i, j, k;
                long[,] a = new long[countVertex, countVertex];
                p = new int[countVertex, countVertex];

                for (i = 0; i < countVertex; i++)
                    for (j = 0; j < countVertex; j++)
                    {
                        if (i == j) a[i, j] = 0;
                        else a[i, j] = int.MaxValue;
                        p[i, j] = -1;
                    }

                foreach (List<int> item in array)
                    a[item[0], item[1]] = item[2];

                for (k = 0; k < countVertex; k++)
                    for (i = 0; i < countVertex; i++)
                        for (j = 0; j < countVertex; j++)
                        {
                            long distance = a[i, k] + a[k, j];
                            if (a[i, j] > distance)
                            {
                                a[i, j] = distance;
                                p[i, j] = k;
                            }
                        }
                return a;
            }

            public void WayFloyd(int a, int b, int[,] p, ref Queue<int> items)
            {
                int k = p[a, b];
                if (k != -1)
                {

                    WayFloyd(a, k, p, ref items);
                    items.Enqueue(k);
                    WayFloyd(k, b, p, ref items);
                }
            }

            public int [] Dijkstr(int v, out int []p)
            {
                int[,] c = new int[countVertex, countVertex];
                for (int i = 0; i < countVertex; i++)
                    for (int j = 0; j < countVertex; j++)
                        c[i, j] = int.MaxValue;

                foreach (List<int> item in array)
                    c[item[0], item[1]] = item[2];

                p = new int [countVertex];
                for (int j = 0; j < countVertex; j++)
                        p[j] = v;
                p[v] = 0;

                int[] distance = new int[countVertex];
                int count, index = 0, u, m = v;

                for (int i = 0; i < countVertex; i++)
                    distance[i] = int.MaxValue;
                distance[v] = 0;

                for (count = 0; count < countVertex - 1; count++)
                {
                    int min = int.MaxValue;
                    for (int i = 0; i < countVertex; i++)
                        if (!nov[i] && distance[i] <= min)
                        {
                            min = distance[i];
                            index = i;
                        }

                    u = index;
                    nov[u] = true;
                    for (int i = 0; i < countVertex; i++)
                        if (!nov[i] && c[u, i] != int.MaxValue && distance[u] != int.MaxValue && distance[u] + c[u, i] < distance[i])//delete
                        {
                            distance[i] = distance[u] + c[u, i];
                            p[i] = u;
                        }
                }
                return distance;
            }

            public void WayDijkstr(int a, int b, int[] p, ref Stack<int> items)
            {
                items.Push(b);
                if (a == p[b]) items.Push(a);
                else WayDijkstr(a, p[b], p, ref items);
            }
        }

        private Node graph;

        public Graph(string nameOfFile)
        {
            StreamReader fin = new StreamReader(nameOfFile);
            int n = int.Parse(fin.ReadLine());
            int m = int.Parse(fin.ReadLine());
            List<List<int>> tmp = new List<List<int>>();
            for (int i = 0; i < n; i++)
            {
                List<int> tmp2 = new List<int>();
                string[] arr = fin.ReadLine().Split(' ');
                for (int j = 0; j < arr.Length; j++)
                    tmp2.Add(int.Parse(arr[j]));
                tmp.Add(tmp2);
            }
            fin.Close();
            graph = new Node(tmp, m);
        }

        public void Floyd()
        {
            int[,] p;
            Console.WriteLine("Введите вершину, из кторой необходимо найти кратчайший путь: ");
            int a = int.Parse(Console.ReadLine()) ;
            Console.WriteLine("Введите вершину, в которую необходимо найти кратчайший путь: ");
            int b = int.Parse(Console.ReadLine()) ;

            long[,] tmp = graph.Floyd(out p);


            if (tmp[a, b] == int.MaxValue)
                Console.WriteLine("Пути из вершины {0} в вершину {1} не существует", a , b );
            else
            {
                Console.WriteLine("Кратчайший путь от вершины {0} до вершины {1} равен {2}, ", a , b , tmp[a, b]);

                Console.Write("Путь: ");
                Queue<int> items = new Queue<int>();
                items.Enqueue(a);
                graph.WayFloyd(a, b, p, ref items);
                items.Enqueue(b);
                while (items.Count != 0)
                    Console.Write("{0} ", items.Dequeue());
                Console.WriteLine();
            }
        }

        public void Dijkstr(int v)
        {
            graph.NovSet();
            int[] p;
            int[] d = graph.Dijkstr(v, out p);
            Console.WriteLine("Длина кратчайшие пути от вершины {0} до вершины", v);
            for (int i = 0; i < graph.Size; i++)
            {
                if ((i != v) && (d[i] != int.MaxValue))
                {
                    Console.Write("{0} равна {1}, ", i, d[i]);
                    Console.Write("путь ");

                    Stack<int> items = new Stack<int>();
                    graph.WayDijkstr(v, i, p, ref items);
                    while (items.Count != 0)
                    {
                        Console.Write("{0} ", items.Pop());
                    }
                }
                Console.WriteLine();
            }
        }

    }
    class Program
    {
        static void Main(string[] args)
        {
            Graph graph1 = new Graph("input.txt");
            Console.WriteLine("Алгоритм Флойда: ");
            Console.WriteLine();
            graph1.Floyd();
            Console.WriteLine();
            Console.WriteLine("Алгортим Дейкстры: ");
            Console.WriteLine();
            graph1.Dijkstr(0);
        }
    }