СиАКОД графы 3

using System;
using System.IO;
using System.Collections.Generic;

namespace Example
{
    class Program
    {
        static void Main()
        {
            Graph g = new Graph("C:/Users/Acer/Desktop/input.txt");
            g.Show();

            Console.Write("Введите число N: ");
            double N = double.Parse(Console.ReadLine());

            g.Task(N);
        }
    };

    public class Graph
    {
        private struct Vertice // структура-вершина
        {
            private string town;
            private int x, y;

            public Vertice(string town, int x, int y)
            {
                this.town = town;
                this.x = x;
                this.y = y;
            }

            public override string ToString()
            {
                return String.Format("({0}, {1}, {2})", town, x, y);
            }

            public double Distance(Vertice v)
            {
                return Math.Sqrt((x - v.x) * (x - v.x) + (y - v.y) * (y - v.y));
            }
        }

        private class Node //вложенный класс для скрытия данных и алгоритмов
        {
            private double[,] array; //матрица смежности
            private Vertice[] vertices; // массив вершин графа

            public int Size //свойство для получения размерности матрицы смежности
            {
                get
                {
                    return array.GetLength(0);
                }
            }

            public Vertice[] Vertices
            {
                get
                {
                    return vertices;
                }
            }

            public double this[int i, int j] //индексатор для обращения к матрице смежности
            {
                get
                {
                    return array[i, j];
                }
                set
                {
                    array[i, j] = value;
                }
            }

            // удаление ребра из графа
            public void Remove(int i, int j)
            {
                array[i, j] = 0.0;
            }

            // добавление ребра в граф
            public void Add(int i, int j)
            {
                array[i, j] = vertices[i].Distance(vertices[j]);
            }

            private bool[] nov; // вспомогательный массив:
                                // nov[v] = true <=> вершина НЕ просмотрена
                                // nov[v] = false <=> вершина просмотрена

            public void NovSet() //метод помечает все вершины графа как непросмотреные
            {
                for (int i = 0; i < Size; i++)
                {
                    nov[i] = true;
                }
            }

            // конструктор вложенного класса, инициализирует матрицу смежности и
            // вспомогательный массив
            public Node(double[,] a, Vertice[] v)
            {
                array = a;
                vertices = v;
                nov = new bool[a.GetLength(0)];
            }

            //реализация алгоритма Флойда
            public double[,] Floyd(out int[,] p)
            {
                int i, j, k;

                //создаем массивы р и а
                double[,] a = new double[Size, Size];
                p = new int[Size, Size];

                for (i = 0; i < Size; i++)
                {
                    for (j = 0; j < Size; j++)
                    {
                        if (i == j)
                        {
                            a[i, j] = 0.0;
                        }
                        else
                        {
                            if (array[i, j] == 0.0)
                            {
                                a[i, j] = double.MaxValue;
                            }
                            else
                            {
                                a[i, j] = array[i, j];
                            }
                        }

                        p[i, j] = -1;
                    }
                }

                //осуществляем поиск кратчайших путей
                for (k = 0; k < Size; k++)
                {
                    for (i = 0; i < Size; i++)
                    {
                        for (j = 0; j < Size; j++)
                        {
                            double distance = a[i, k] + a[k, j];
                            if (a[i, j] > distance)
                            {
                                a[i, j] = distance;
                                p[i, j] = k;
                            }
                        }
                    }
                }

                return a; //в качестве результата возвращаем массив кратчайших путей между
            }             //всеми парами вершин

            //восстановление пути от вершины a до вершины b для алгоритма Флойда
            public void WayFloyd(int a, int b, int[,] p, ref Queue<Vertice> items)
            {
                int k = p[a, b];

                //если k != -1, то путь состоит более чем из двух вершин а и b, и проходит через
                //вершину k, поэтому
                if (k != -1)
                {
                    // рекурсивно восстанавливаем путь между вершинами а и k
                    WayFloyd(a, k, p, ref items);
                    items.Enqueue(vertices[k]); //помещаем вершину к в очередь
                                                // рекурсивно восстанавливаем путь между вершинами k и b
                    WayFloyd(k, b, p, ref items);
                }
            }
        } //конец вложенного клаcса

        private Node graph; // закрытое поле, реализующее АТД «граф»

        public int Size    // свойство для получения размерности матрицы смежности
        {
            get
            {
                return graph.Size;
            }
        }

        public Graph(string name) //конструктор внешнего класса
        {
            using (StreamReader file = new StreamReader(name))
            {
                int n = int.Parse(file.ReadLine());
                double[,] a = new double[n, n];
                Vertice[] v = new Vertice[n];

                for (int i = 0; i < n; ++i)
                {
                    string line = file.ReadLine();
                    string[] mas = line.Split(" ");

                    string town = mas[0];
                    int x = int.Parse(mas[1]), y = int.Parse(mas[2]);

                    v[i] = new Vertice(town, x, y);
                }

                for (int i = 0; i < n; i++)
                {
                    string line = file.ReadLine();
                    string[] mas = line.Split(" ");

                    for (int j = 0; j < n; j++)
                    {
                        int cur = int.Parse(mas[j]);

                        if (cur == 1) a[i, j] = v[i].Distance(v[j]);
                    }
                }

                graph = new Node(a, v);
            }
        }

        // метод выводит матрицу смежности на консольное окно
        public void Show()
        {
            Console.WriteLine("n = {0}", graph.Size);

            for (int i = 0; i < graph.Size; i++)
            {
                for (int j = 0; j < graph.Size; j++)
                {
                    Console.Write("{0:f2}\t", graph[i, j]);
                }

                Console.WriteLine();
            }
        }

        public void Task(double N)
        {
            int[,] p0;
            double[,] a0 = graph.Floyd(out p0);


            for (int i = 0; i < graph.Size; ++i)
                for (int j = 0; j < graph.Size; ++j)
                    if (graph[i, j] != 0.0)
                    {
                        graph.Remove(i, j);

                        int[,] p;
                        double[,] a = graph.Floyd(out p);

                        bool ok = true;

                        for (int k = 0; k < graph.Size && ok; ++k)
                            for (int l = 0; l < graph.Size && ok; ++l)
                                if (a0[k, l] != double.MaxValue && a[k, l] > N) ok = false;

                        if (ok)
                        {
                            Console.WriteLine("Да! Возможно!");
                            Console.WriteLine("Удалим ребро {0} - {1}. Тогда:\n", graph.Vertices[i].ToString(), graph.Vertices[j].ToString());

                            for (i = 0; i < graph.Size; ++i, Console.Write("\n"))
                                for (j = 0; j < graph.Size; ++j)
                                    if (a[i, j] == double.MaxValue)
                                        Console.WriteLine("{0} -> {1}: не существует", graph.Vertices[i].ToString(), graph.Vertices[j].ToString());
                                    else
                                    {
                                        Console.Write("{0} -> {1} = {2:f2}; ", graph.Vertices[i].ToString(), graph.Vertices[j].ToString(), a[i, j]);

                                        Console.Write("путь: ");

                                        Queue<Vertice> items = new Queue<Vertice>();

                                        items.Enqueue(graph.Vertices[i]);
                                        graph.WayFloyd(i, j, p, ref items);
                                        items.Enqueue(graph.Vertices[j]);

                                        while (items.Count != 1)
                                            Console.Write("{0} - ", items.Dequeue().ToString());

                                        Console.Write("{0}\n", items.Dequeue().ToString());


                                    }

                            return;
                        }
                        else graph.Add(i, j);
                    }

            Console.WriteLine("Удалить ребро, так, чтобы сохранялись все условия, невозможно");
        }
    };
}

/*
Test #1:
5
A 8 -1
B 3 -7
C -7 7
D -8 -6
D -3 -8
0 0 0 0 1
0 0 1 1 0
0 1 0 0 1
0 0 1 0 0
1 1 1 0 0
*/