Нахождение кратчайшего пути в графе. Алгоритм Дейкстры C#

Описание требований к программе

Требования к функциям системы

Система должна представлять приложение для ПК под управление Windows 10 и обеспечить следующий функционал:

• Создание пользователем или автоматическая генерация игрового поля с графом, ребра которого имеют веса;
• Сохранение созданных графов в отдельный файл;
• Автоматический поиск меньшего по весу ребер маршрута на графе;
• Пользовательское меню, которое позволяет выбирать-нужно ли пользователю сохранить граф, создать граф вручную, сгенерировать определенный граф;
• Предоставлять пользователю возможность строить маршруты на графе для последующего их сравнения с кратчайшим маршрутом, который был найден автоматически; 
• Предоставлять возможность пользователю назначать числовые диапазоны, в которых будут автоматически генерироваться ребра графа;
• Предоставлять возможность пользователю самостоятельно выбирать количество вершин, из которых будет создан граф;

Язык программирования

Исходным ЯП является С#.

Назначение программы

Программа предназначена для создания или автоматической генерации графов со взвешенными ребрами в 2-х мерной графике, сохранения графов в отдельный файл, построения пользователем маршрута, рекурсивного автоматического поиска оптимального маршрута, и сравнения маршрута, найденного автоматически с маршрутом, построенным пользователем.

Программа решает следующие задачи: 

• Создание или автоматическая генерация игрового поля;
• Сохранение созданных полей в отдельный файл;
• Поиск кратчайшего маршрута на графе;
• Сравнение пользовательского маршрута и найденного кратчайшего маршрута на графе; 

Приблизительный вид графа на игровом поле:

Серым цветом закрашены заблокированные для обхода вершины.

Макет главного меню программы:

Примерный макет пользовательского интерфейса в главном меню программы.

Назначение элементов управления:

• Кнопка «Создать граф вручную» предназначена для создания на игровом поле графа в ручном режиме (с указанием количества вершин наличия ребер, их весов, а также строения графа и весов вершин).
• Кнопка «Автоматически сгенерировать граф» открывает игровое поле и создает случайный взвешенный граф в автоматическом режиме (с указанием числового диапазона генерации весов ребер, а также количества вершин).
• Кнопка «Открыть граф из файла» открывает проводник windows и затем пользователю нужно выбрать необходимый для открытия граф.

Создание графа:

Красным цветом выделены параметры, которые пользователь задает в ручную

После ввода всех необходимых параметров и нажатия кнопки «создать граф»-генерируется граф по пользователем заданным параметрам.

Выбор кратчайшего пути пользователем происходит поочередным нажатием на круги с номерами вершин-(путь между ними подсвечивается красным цветом)

При поочередном нажатие на вершину 2, а затем на вершину 1, ребро между ними становится красным(также подсвечиваются и сами вершины)-при нажатии кнопки сброс выделения вершин-все действия отменяются-происходит сброс выделения вершин и пути между ними-пользователь может заново выбирать путь

При поочередном нажати на вершины 2, 1, а затем на кнопку проверить путь происходи автоматический поиск кратчайшего маршрута, найденный автоматически маршрут сверяется с выбранным пользователем, затем выдается сообщение-успех!, кратчайший путь найден!,если найденный автоматически маршрут соответствует пользовательскому, или сообщение о том что маршрут был не кратчайшим

При нажатии кнопки-найти кратчайший путь происходит автоматический поиск кратчайшего пути, а затем подсвечиваются вершины и ребра через которые и был построен кратчайший путь

Для упрощения визуальной работы с графом- вершины должны распологаться кругом на одинаковом расстояннии друг от друга – чтобы избежать накладывания вершин друг на друга

Фрагмент программного кода:

private void button_CreateGraph_Click(object sender, EventArgs e)
        {
            //считываем введенные данные
            var vertexCount = Convert.ToInt32(numericUpDown_VertexCount.Value);
            var weightFrom = Convert.ToInt32(numericUpDown_WeightFrom.Value);
            var weightTo = Convert.ToInt32(numericUpDown_WeightTo.Value);

            //объявляем генератор случайных чисел
            var random = new Random();
            //объявляем матрицу нужно размерности
            var matrix = new int[vertexCount, vertexCount];
            //идем по каждой строке матрицы
            for (int i = 0; i < vertexCount; i++)
            {
                //идем по каждой ячейке i-ой строки матрицы
                for (int j = 0; j < vertexCount; j++)
                {
                    //если ячейка на главной диагонали,
                    if (i == j)
                    {
                        //то идем смтореть следующую
                        continue;
                    }
                    //Если ячейка слева от диагонали,
                    if (i > j)
                    {
                        //то пишем в нее случайное число из заданного пользователе диапазона
                        matrix[i, j] = random.Next(weightFrom, weightTo);
                        //и дублируем это значения в симметричную ячейку
                        matrix[j, i] = matrix[i, j];
                    }
                }
            }

            //запоминаем введенную матрицу
            GameParameters = new GameField();
            GameParameters.Matrix = matrix;

            //говорим, что работа на этой форме окончена и закрываем ее (управление передается обратно на главную форму)
            this.DialogResult = DialogResult.OK;
        }
    }

Содержание архива:

• Исходник программы на языке программирования C# (Win Forms) для Visual Studio