Алгоритм Форда-Беллмана

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

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

Курсовая работа

Алгоритм Форда-Беллмана

Выполнил Анастасин В.

Введение

Алгоритм Форда-Беллмана - алгоритм поиска кратчайшего пути во взвешенном графе.

История алгоритма связана сразу с тремя независимыми математиками: Лестером Фордом, Ричардом Беллманом и Эдвардом Муром. Форд и Беллман опубликовали алгоритм в 1956 и 1958 годах соответственно, а Мур сделал это в 1957 году. И иногда его называют алгоритмом Беллмана - Форда - Мура. Метод используется в некоторых протоколах дистанционно-векторной маршрутизации, например в RIP (Routing Information Protocol - Протокол маршрутной информации).

Также как и алгоритм Дейкстры, алгоритм Беллмана -- Форда вычисляет во взвешенном графе кратчайшие пути от одной вершины до всех остальных. Он подходит для работы с графами, имеющими ребра с отрицательным весом. Но спектр применимости алгоритма затрагивает не все такие графы, ввиду того, что каждый очередной проход по пути, составленному из ребер, сумма весов которых отрицательна (т. е. по отрицательному циклу), лишь улучшает требуемое значение. Бесконечное число улучшений делает невозможным определение одного конкретного значения, являющегося оптимальным.

В качестве среды разработки мною была выбрана среда Microsoft Visual Studio 2017, язык программирования - С++.

В ходе выполнения данной курсовой работы были приобретены навыки работы с формами и их элементами в среде Microsoft Visual Studio 2017, навыки работы с проектами и многомодульными программами.

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

Требуется разработать программу, которая находит кратчайший путь во взвешенном графе, используя алгоритм Форда-Беллмана.

Исходный граф в программе должен задаваться матрицей смежности, причём при вводе данных должны быть предусмотрены граничные условия, должна выполняться проверка корректности введенных данных. Устройства ввода данных - клавиатура и мышь. Программа должна быть разработана для работы в операционной системе Microsoft Windows. Для удобства использования программы должен быть разработан графический интерфейс оформленный в windows.forms с возможностью ввода и вывода информации.

Задания выполняются в соответствии с вариантом №2.

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

Пусть нам дана матрица весов С(D) орграфа D и начальная вершина s. Найдем расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v О V.

1. Всем вершинам vОV орграфа присвоим метку D[v] = csv. Вершине s присвоим метку D[s] = 0.

2. Положим k=1.

3. Выберем произвольную вершину vО V \ {s}.

4. Выберем произвольную вершину u ОV.

5. Положим D[v] = min (D[v], D[u] + cuv).

6. Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.

7. Если вершина v пробежала еще не все множество вершин V \ {s}, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.

8. Если k < n-2, то положить k=k+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D[v] будут равны расстояниям d(s,v) в орграфе D.

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

По алгоритму Форда-Беллмана (это алгоритм который способствует поиску кратчайшего пути во взвешенном графе, благородя ему мы сможем найти оптимальный путь во взвешенном графе и определить минимальное расстояние между рёбрами имеющие вес. берем вершину и проверяем если возможно пройти через нее и это будет короче чем идти напрямик, то сохраняем длину пути через эту вершину) мы проверяем на прочность все связи, иными словами -- мы проходим все ребра и проверяем условие. Если существует альтернативный путь от одной вершины к другой, то будет ли он будет короче если да, то мы его заменяем. Таким алгоритмом мы находим все кротчайшие пути через вершины. Но в ответе должен быть максимальный из путей через вершины, поэтому приходится снова пройтись по путям через вершины (но это уже не ребра, а оптимальные длины путей) и найти кратчайший путь максимальной длины.

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

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

На Рисунке 2 показана схема работы алгоритма Форда-Беллмана.

Рисунок 2 - Схема Алгоритма Форда-Беллмана.

Ручной расчёт задачи

Определим минимальные пути из вершины v1 до всех остальных вершин в нагруженном орграфе D, изображенном на рис. 3.

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

Ниже в таблице приведены матрица весов, а также все вычисления по шагам. Матрица весов изображена на рисунке 4.

Рисунок 4 - Матрица весов.

На первом шаге всем вершинам vV орграфа присвоим метку D[v] = csv, где s = v1. Выберем следующую вершину v2. Ей присвоим метку D[v2] = min (D[v2], D[u] + cuv), где u V, т.е. D[v2] = min (D[v2], D[v3]+ c32, D[v4]+ c42, D[v5]+ c52, D[v6]+ c62) = (,5+2, 5+2, 2+, 12+) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.

Аналогично корректируются метки всех оставшихся вершин, а именно,

D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+, 5+, 2+1, 12+) = 3,

D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+, 3+, 2+2, 12+) = 4,

D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+, 3+, 4+, 12+) = 2,

D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+, 4+, 2+) = 9.

Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.

Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1 до всех остальных вершин. Например, длина минимального пути из v1 в v2 равна 5, сам путь имеет вид: v1v5v3v2.

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

алгоритм форда беллман

Программа разбита на несколько модулей. Логика.cpp - главный файл проекта. В нем осуществляется запуск главного окна Form1().

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

На рисунке 5 изображено стартовое окно программы:

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

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

На рисунке 6. Показан результат работы программы.

Рисунок 6 - Результат работы программы.

Тестирование

Проведём различные тесты с программой использую различные символы для исходной матрицы инцидентности. В процессе тестирования программы проверялась реакция программы на введенные значения.

На рисунке 7 мы можем наблюдать реакцию программы на ввод некорректных символов.

Рисунок 7 - Обработка ошибки при вводе буквы.

На рисунке 8 изображена реакция программы на превышение максимального значения

Рисунок 8 - Результат при корректном вводе.

На рисунке 9 изображен результат работы программы при корректном вводе значений.

Рисунок 9 - Результат при корректном вводе.

Заключение

В ходе данного курсового проекта был изучен и реализован алгоритм Форда-Беллмана для нахождение кратчайших путей между парами вершин в ориентированном графе, исходя из матрицы инцидентности.

При выполнении данной работы использовались функции Windows.form, описанные в заголовочном файле Windows.h для визуализации результатов работы.

Во время выполнения курсового проекта был использован такой приём как выделение динамической памяти.

В ходе тестирования были выявлены основные преимущества и недостатки изучаемого алгоритма.

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

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

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

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

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

Приложение. Результаты работы программы на разных наборах исходных данных

Результаты работы программы показаны на Рисунках 10-12.

Рисунок 10 - Результат работы программы

Рисунок 11 - Результат работы программы

Рисунок 12 - Результат работы программы.

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