МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ
ХАРКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ
Кафедра информатики
КУРСОВАЯ РАБОТА
Тема: “Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)”
по дисциплине «Программирование»
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Выполнил: Руководители:
Студент группы КИ-05-4 Руденко Д. А.
Петров О. В. Машталир С. В.
Харьков 2006
РЕФЕРАТ
Записка объяснительная к курсовой работе: 23с., 5 рис., 1 табл., 5 разделов, 3 приложения.
Объект исследования – граф с взвешенными дугами.
Цель работы – разработка демонстрационной программы использования алгоритма Дейкстры.
Метод исследования – изучение литературы, составление и отладка программы на компьютере.
Данную программу можно использовать для поиска кратчайших расстояний между двумя точками.
Программа составлена на языке С++ в среде Microsoft Visual C++ 6.0. Ключевые слова: АЛГОРИТМ ДЕЙКСТРЫ, ГРАФ, ВЕРШИНА, РЕБРО, ВЕС, ПУТЬ, МАССИВ, МЕТКА, ПРОГРАММА, ТИП, ОПЕРАТОР, ФУНКЦИЯ, ЦИКЛ, МАТРИЦА СМЕЖНОСТИ.
СОДЕРЖАНИЕ
Введение………………………………………………………....…… 4 1 Постановка задачи и сфера её применения…..………………...... 6 2 Теоретическая часть…………………………………….………..... 7 2.1 Общие сведения о графах……………………………...……. 7 2.2 Алгоритм Дейкстры….……………………………………... 9 3 Особенности работы в среде ……………………….……………. 10 4 Программная реализация………………………………….……. 11 4.1 Описание алгоритма и структуры программы…………….. 11 4.2 Описание программных средств……………………………. 13 5 Инструкция пользователя…………………………………………. 15 Заключение….…………………………………………………….…. 16 Перечень ссылок……………………………………………………... 17 Приложение А Текст программы………………………………….. 18 Приложение Б Результат………..……………………………….….. 22 Приложение В Схема программной реализации алгоритма Дейкстры….. 23
ВВЕДЕНИЕ
Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.
Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.
Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:
· алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);
· алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);
· алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).
Указанные алгоритмы легко выполняются при малом количестве вершин в графе. ............
