ВВЕДЕНИЕ 5
ГЛАВА 1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ 6
1.1 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 6
1.2 АЛГОРИТМ ДЕЙКСТРЫ 8
1.2.1 Краткие сведения об алгоритме 8
1.2.2 Формулировка задачи 9
1.2.3 Идея решения 9
1.2.4 Псевдоалгоритм 9
1.2.5 Пример работы алгоритма Дейкстры 10
ГЛАВА 2 РАЗРАБОТКА ПРИЛОЖЕНИЯ В СРЕДЕ DELPHI 13
2.1 СРЕДА РАЗРАБОТКИ DELPHI 13
2.2 ПОСТАНОВКА ЗАДАЧИ ПРОЕКТИРОВАНИЯ 17
2.3 РАЗРАБОТКА ВИЗУАЛЬНОГО ИНТЕРФЕЙСА ПОЛЬЗОВАТЕЛЯ 18
2.4 СТРУКТУРЫ ДАННЫХ 20
2.5 РАЗРАБОТКА ОБРАБОТЧИКОВ СОБЫТИЙ, АЛГОРИТМОВ И ПРОГРАММНОГО КОДА 22
2.5.1 Описание процедуры задания матрицы смежности 22
2.5.2 Процедура нахождения кратчайшего пути 23
2.6 ТЕСТИРОВАНИЕ ПРОГРАММЫ 26
ЗАКЛЮЧЕНИЕ 27
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 28
ПРИЛОЖЕНИЕ 29
ПРОГРАММНЫЙ ЛИСТИНГ ПРИЛОЖЕНИЯ 29
В процессе создания данного курсового проекта изучены алгоритм Дейкстры и среда программирования Delphi. Также разработана программа, реализующая алгоритм Дейкстры в Delphi 10 Lite.
В первой главе рассмотрены теоретические сведения, которые необходимы для создания программы и реализации алгоритма. К ним относятся: основные понятия теории графов, краткие сведения об алгоритме, общая формулировка задачи о поиске кратчайшего пути, идея решения этой задачи. В данной главе приведен псевдоалгоритм для реализации программы. На примере подробно разобрано как работает алгоритм Дейкстры.
Вторая глава содержит информацию о среде разработки – Delphi. Здесь рассматривается постановка задачи проектирования, разработка визуального интерфейса пользователя, обработчики событий. Рассматривается структура для хранения данных в программе. Описаны процедуры задания матрицы смежности и нахождения кратчайшего пути. Также в этой главе проведено тестирование программы.
Данную работу можно использовать при изучении языка программирования Delphi. так как в ней изложены основные моменты для работы в этой среде. Кроме того, разработанная программа может использоваться в дискретной математике для исследования графов или в качестве наглядного пособия, демонстрирующего применение алгоритма Дейкстры на практике.
Алгоритм Дейкстры также широко применяется в жизни.
Примеры
1. При эвакуации населения из очагов бедствия оптимальные маршруты до пунктов сбора транспорта для каждой группы людей (дом, улица, школа и т.д) в штабе МЧС рассчитывает программа на основе алгоритма Дейкстры.
2. Дана сеть автомобильных дорог, соединяющих города Московской области. Некоторые дороги односторонние. Найти кратчайшие пути от города Москва до каждого города области (если двигаться можно только по дорогам).
3. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.
1. Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий / С.Д. Шапорев. – СПб.: БВХ-Петербург, 2007. – 400 с.: ил.
2. Плотников, А.Д. Дискретная математика: учеб. пособие / А.Д. Плотников. – 3-е изд., испр. и доп. – Минск: Новое знание, 2008. – 320 с.
3. Фаронов, В.В. Delphi. Программирование на языке высокого уровня: учебник для вузов / В.В. Фаронов. – СПб.: Питер, 2006. – 640с.: ил.
4. Алгоритмы: построение и анализ – Кормен [и др.] ; под общ. ред. И.В. Красикова. – 2-е издание.: Пер. с англ. – М.: Издательский дом “Вильямс”, 2005. – 1296 с.: ил. – Парал. тит. англ.
5. Алгоритм Дейкстры / Википедия [Электронный ресурс]. – 2013. – Режим доступа: http://ru.wikipedia.org/wiki/Алгоритм Дейкстры. – Дата доступа: 10.02.2020.
