Алгоритм Дейкстры

Размещено на http://www.allbest.ru/

Министерство образования Российской Федерации

Пензенский государственный университет

Кафедра «Вычислительная техника»

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

к курсовой работе

по курсу «Логика и основы алгоритмизации в инженерных задачах»

на тему «Алгоритм Дейкстры»

Выполнил:

Студент группы 16ВВ1

Борискин Вячеслав

Приняли:

д.т.н., профессор Пащенко Д.В.

Пенза 2017

Оглавление

Введение

1. Теоретическая часть программы

1.1 Общие теоретические сведения

1.2 Описание алгоритма программы

2. Ручной расчёт программы

3. Описание программы

4. Тестирование проекта. Обработка некорректных данных

Список литературы

Введение

Алгоритм Дейкстры -- алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS. Данный алгоритм находит очень широкое применение в практической деятельности. Он очень подходит для работы с системами, которые имеют множество связанных между собой точек - вершин.

Эдсгер Дейкстра Родился 11 мая 1930 года в Роттердаме, в семье учёных (отец -- химик, мать -- математик).

В 1951 году увлёкся программированием, поступил на трёхнедельные компьютерные курсы в Кембридже. Изобрёл новое правило компиляции -- «вызов по имени».

В 1960-е годы участвовал в создании операционной системы THE построенной в виде множества параллельно исполняющихся взаимодействующих процессов. Именно в ходе этой работы появились понятия синхронизации процессов, идея семафора, а также была чётко осознана необходимость в структуризации процесса программирования и самих программ.

Разработал основные положения структурного программирования.

Мною была выбрана среда программирования «Microsoft Visual Studio 2010», язык программирования - С++.

В процессе выполнения работы мною были приобретены навыки работы с формами и их элементами, а также с языком программирования С++.

Постановка задачи

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

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

Устройства ввода и вывода информации: мышь, клавиатура. Программа должна быть разработана для работы в ОС Microsoft Windows.

Задание выполнено в соответствии с вариантом 1.

1. Теоретическая часть программы

1.1 Общие теоретические сведения

Данные: матрица весов С(D) орграфа D, начальная вершина s.

Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v V, а также последовательность вершин, определяющая кратчайший путь из s в v .

1. Положим l*(s) = 0 и будем считать эту метку постоянной. Для всех v V, v s, положим l*(v) = и будем считать эти метки временными. Положим p = s.

2. Для всех vГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и (v) =р. Иначе l*(v) и (v) не менять, т.е. l*(v) = min (l*(t), l*(p)+cpv). (Идея состоит в следующем: пусть p - вершина, получившая постоянную метку l*(p) на предыдущей итерации. Просматриваем все вершины vГp, имеющие временные метки. Метка l*(v) вершины vГp заменяется на l*(p)+l(p,v), если оказывается, что ее метка l*(v)>l*(p)+l(p,v). В этом случае говорим, что вершина v получила свою метку из вершины p, поэтому положим (v) = p. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l*(v) l*(p)+cpv, то метки остаются прежними.

3. Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что l*(v*) = min l*(v), v ?V*. Считать метку l*(v*) постоянной для вершины v*.

4. Положим p = v*. Если p = t, то перейдем к п.5 ( l*(t) - длина минимального пути ). Иначе перейдем к п.2.

5. Найдем минимальный путь из s в t, используя метки (v): П = s…(t)t.

1.2 Описание алгоритма программы

Разобьем все вершины на два множества: уже обработанные и еще нет. Изначально все вершины необработанные, и расстояния до всех вершин, кроме начальной, равны бесконечности, расстояние до начальной вершины равно 0.

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

Релаксация ребра (u, v) заключается в присваивании dist[v] = min(dist[v], dist[u] + w[u, v]), где dist[v] -- расстояние от начальной вершины до вершины v, а w[u, v] -- вес ребра из u в v.

На Рисунке 1 показана схема работы программы.

Рисунок 1 - Схема программы.

Рисунок 2 Схема Алгоритм Дейкстры

2. Ручной расчёт программы

Пример. Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рисунке 3. Все вычисления будем проводить с помощью матриц D, изображённых на Рисунках 4-7.

Рисунок 3 - Орграф.

m = 1 m = 2

Рисунок 4 - Матрицы D.

Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения, т.к. D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ). Поэтому рассмотрим случай, когда i = 2 , а j = 3. Тогда D[2,3] = min ( D[2,3], D[2,1] + D[1,3] ) = min (,+5) = . Далее, j = 4, т.е. D[2,4] = min(D[2,4], D[2,1] + D[1,4] ) = min (,+5) = . Продолжаем процесс до тех пор, пока i 6 и j 6. Положим m = 2 и продолжим рассуждения дальше. m = 3 m = 4

Рисунок 5 - Матрицы D.

m = 5 m = 6

Рисунок 6 - Матрицы D.

Рисунок 7 - Матрица D.

3. Описание программы

Файл 1.срр - главный файл проекта. В нём осуществляется запуск основного окна Form1.h

Файл Form1.h отвечает за дизайн и интерфейс программы. В нём осуществляется ввод данных, а именно: количество вершин, стартовая вершина и матрица весов. Также в нём выполняется сам алгоритм Дейкстры.

Рисунок 8 Стартовое окно программы

На рисунке 6 вы можете видеть стартовое окно программы.

Рисунок 9 Вычисление кратчайших расстояний

программа алгоритм дейкстра вершина

На рисунке 9 вы можете видеть результат работы программы. После нажатия на кнопку «Вычислить!» выполняется алгоритм, и в поле «Ответ» записываются результаты вычислений.

4. Тестирование проекта. Обработка некорректных данных

В процессе тестирования проверялась правильная реакция программы на неверно введённые данные

Рисунок 10 Стартовая вершина не найдена

На рисунке 10 вы можете видеть реакцию программы на ввод стартовой вершины, большей чем количество вершин.

Рисунок 11 Реакция программы на несуществующий путь

На рисунке 11 мы видим реакцию программы на ситуацию, когда между вершинами нет пути.

Список литературы

1. Брайан Керниган, Деннис Ритчи - Язык программирования Си, 2-е издание, 2016.

2. Брюс Эккель - Философия C++. Введение в стандартный C++, 2-е издание, 2004.

3. Стивен Прата - Язык программирования C++. Лекции и упражнения, 6-е издание, 2017.

4. Электронный ресурс: https://msdn.microsoft.com/ru-ru/. Дата обращения: 01.11.2017.

Размещено на Allbest.ru