Сейчас работаем

Нахождение кратчайшего пути в графе. Алгоритм Дейкстры 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

Купить 4500,00 
(без учета комиссии 3,8 %)
Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически.
Похожие работы
Тип Название Рейтинг Категория Стоимость
Курсовая Нахождение кратчайшего пути в графе. Алгоритм Дейкстры C#. 1 .NET (C#) 990,00
Исходник Нахождение эйлеровых циклов в графе С++ 0 C/C++ 800,00
Курсовая Реализация алгоритма Дейкстры-Прима С# 0 .NET (C#) 1 500,00
Другие работы автора
Тип Название Рейтинг Категория Стоимость
Исходник Нахождение эйлеровых циклов в графе С++ 0 C/C++ 800,00
Курсовая Автоматическое реферирование текста C# 5 .NET (C#) 3 700,00
Курсовая Автоматическое составление кроссвордов С++ 0 .NET (C#) 2 700,00
Комментарии (0)

klausms

/ /

Оставить комментарий

Ты не можешь комментировать

Только зарегистрированые пользователи имеют возможность комментировать работы
Купить

4500,00 

(без учета комиссии 3,8 %)

Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически.
ShortestPathOnGraph.rar
89264
Оцени работу

рейтинг

Поделись работой с друзьями

Категории
Нахождение кратчайшего пути в графе. Алгоритм Дейкстры C#
Графы C#, поиск кратчайшего пути, Алгоритм Дейкстры
Категория: Образование
Стоимость: 4500,00