Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

КУРСОВАЯ РАБОТА

Тема: “Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)”

по дисциплине «Программирование»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

 

Выполнил: Руководители:

Студент группы КИ-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-оптимальных маршрутов между двумя вершинами).

Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется. Здесь на помощь приходит современная техника

Компьютерные средства и информационные технологии повысили возможности такого всеохватывающего метода изучения и создания, как моделирования объектов, явлений и процессов – как тех, что существуют в природе, так и тех, что создаются человеком искусственно.

Количество объектов усложнялись, увеличивались, и натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства, формулы и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

Реализовать большой потенциал математического моделирования невозможно без мощных средств автоматизации вычислений, которыми являются компьютеры. Благодаря появлению компьютеров и развитию информационных технологий создаются методы и средства компьютерного моделирования, способные решать сложные практические задачи, такие как управление большими энергетическими системами, создание достоверных прогнозов погоды или урожая, моделирование региональных и общегосударственных систем, проектирование самолетов, кораблей и т. п. Компьютерная модель – это размещенная в компьютере совокупность средств, что реализуют концепцию вычисления.

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

Большие программы из-за своей сложности нередко содержат ошибки, которые могут стать причиной материального ущерба, а иногда и угрожать жизни людей (например, при управлении авиаполётами). В результате борьбы с проблемой сложности программного кода были выработаны три новые концепции программирования:

а) объектно-ориентированное программирование (ООП);

б) унифицированный язык моделирования (UML);

в) специализированные средства разработки программного обеспечения;

Из всех объектно-ориентированных языков С++ является наиболее широко используемым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстры.

1 ПОСТАНОВКА ЗАДАЧИ И СФЕРА ЕЁ ПРИМЕНЕНИЯ

Основной задачей данного курсового проекта является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.

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

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