На нашем сайте Вы сможете найти готовые курсовые и дипломные работы по программированию
Сейчас работаем

Нахождение кратчайшего пути в графе. Алгоритм Дейкстры 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 
Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически. Исходник программ Вы сможете отредактировать, как Вам нужно.
Комментарии (0)

klausms

/ /

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

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

Только зарегистрированые пользователи имеют возможность комментировать работы
Другие работы автора
Тип Название Рейтинг Категория Стоимость
Исходник Нахождение эйлеровых циклов в графе С++ 0 C/C++ 800,00
Курсовая Автоматическое реферирование текста C# 5 .NET (C#) 3 700,00
Курсовая Автоматическое составление кроссвордов С++ 0 .NET (C#) 2 700,00
Исходник Алгоритм Рабина-Карпа C# 0 .NET (C#) 1 500,00
Исходник Алгоритм Хаффмана C# 22 .NET (C#) 3 500,00
Новые работы
Тип Название Рейтинг Категория Стоимость
Диплом Разработка Telegram-бота для колледжа АГУ (Python) new 0 Python 10 000,00
Исходник Учёт товаров (Python, Tkinter, Sqlite) new 0 Python 3 000,00
Курсовая АИС "Авиакасса" (C#, WPF, WinForms, SQLite, SQL Server, Access) new 0 .NET (C#) 5 500,00
Курсовая Курсовая работа разработка мобильных приложений "FTP клиент для Android" new 0 Сетевые протоколы 6 500,00
Исходник Транспонирование матрицы new 0 .NET (C#) 150,00
Купить

4500,00 

Покупается впервые!
Сразу после оплаты Вы получите работу на электронную почту. Файлы отправляются автоматически. Исходник программ Вы сможете отредактировать, как Вам нужно.
ShortestPathOnGraph.rar
89264
Оцени работу

рейтинг

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

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