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

Граф - это совокупность множества вершин и множества пар вершин (связей между вершинами, дуг). Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd ) и Стивена Уоршелла (Stephen Warshall ) в 1962 г., хотя в 1959 г. Алгоритм Флойда делает N итераций, после i-й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до i-й. Как и любой базовый алгоритм, алгоритм Флойда - Уоршелла используется очень широко, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами. Если граф не содержит ребер с отрицательным весом, то можно использовать алгоритм Дейкстры для нахождения кратчайшего пути от одной вершины до всех остальных, запустив его на каждой вершине.На рисунке 1 представлена разработанная блок-схема алгоритма Флойда, где показано, каким образом, работает этот алгоритм. i, j, k, - аргументы прохода по циклу, N - размер массива расстояний, D[N][N] - массив расстояний. На рисунке 2 представлена разработанная блок-схема алгоритма Беллмана-Форда, где показано, каким образом, работает этот алгоритм. Smej - матрица смежности графа, start_v - начальная вершина, MRAST - массив существующих в графе дуг, rez - массив кратчайших расстояний, RELAX(rez[MRAST[j].to]) - улучшение пути между начальной и j-ой вершиной графа. На рисунке 4 приведена часть псевдокода, где описано вычисление матрицы кратчаших путей; будем улучшать путь через k-ю вершину, если пойти из i в k, а из k в j выгоднее, чем пойти напрямую из i в j, то запоминаем этот путь. На рисунке 6 приведена часть псевдокода, где производится ввод n - количество вершин в графе, m - количество дуг в графе, start_v - начальная вершина, Smej - матрица смежности графа G(n,m).Время выполнения программы по алгоритму Флойда состовляет O(n^3), так как в ней нет практически ничего, кроме 3 вложенных друг в друга циклов. Наилучшим случаем для алгоритма станет граф в котором всего нет улучшения пути, т. е. вводимая матрица расстояний не изменится после выполнения программы. В этом случае время выполнения программы составит O(n^3). Наихудшим случаем для алгоритма станет граф с отрицательным циклом.Заполнение матрицы расстояний осуществляем при помощи чтения текстового файла «ALGF .txt», заполненная матрица представлена на рисунке 11. На рисунке 12 представлен вывод матрицы кратчайших расстояний заданного графа, помимо матрицы показано время работы программы в секундах. Заполнение матрицы расстояний осуществляем при помощи чтения текстового файла «ALGBF .txt» В том же рисунке показано время работы программы.Протокол тестирования правильности работы программы по алгоритму Флойда содержится в таблице 1. В входных данных вводится матрица расстояний, так же матрицу ожидаем получить и в выходных данных.Протокол тестирования правильности работы программы по алгоритму Беллмана-Форда содержится в таблице 2. В входных данных вводится матрица расстояний, так же матрицу ожидаем получить и в выходных данных. В 4 и 5 примерах используются ребра отрицательного веса, где последний задает граф с циклом отрицательного веса.5 0 inf-3 inf 2 0 inf inf inf 7 0-1-6 inf inf 0 В графе есть цикл отрицательного веса.Анализ по времени проводится функцией clock() из стандартной библиотеки .Проанализируем результаты, алгоритмы Флойда и Беллмана-Форда очень похожи по своей структуре и поиску кратчайших путей, они различаются по хранению промежуточной информации о кратчайших путях.Для достижения поставленной цели потребовалось реализовать алгоритмы Флойда и Беллмана-Форда в среде (программе) Microsoft Visual Studio. При создание кода программы использовалась программа Microsoft Visual Studio 2008. В результате при помощи созданной программы была получена возможность нахождения минимального расстояния между всеми вершинами, при случайном распределении длин ребер, при ручном вводе и вводе при помощи файла.

Содержание

Введение

1 Разработка блок-схемы алгоритмов

2 Разработка псевдокода алгоритмов

3 Анализ трудоемкости роста функции

4 Программа реализации алгоритмов

5 Тестирование программ реализации алгоритмов

5.1 Тестирование правильности

5.2 Анализ по времени

6 Анализ результатов

Заключение

Список использованных источников

Приложение А Код программы по алгоритму Флойда

Приложение Б Код программы по алгоритму Беллмана-Форда

Алгоритм Флойда поиска кратчайших путей между всеми парами вершин.

Граф - это совокупность множества вершин и множества пар вершин (связей между вершинами, дуг).

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

Этот алгоритм был одновременно опубликован в статьях Роберта Флойда (Robert Floyd ) и Стивена Уоршелла (Stephen Warshall ) в 1962 г., хотя в 1959 г. Бернард Рой (Bernard Roy ) опубликовал практически такой же алгоритм, но это осталось незамеченным.

Алгоритм Флойда делает N итераций, после i-й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до i-й. На каждой итерации перебираются все пары вершин и путь между ними сокращается при помощи i-й вершины. Перед работой алгоритма матрица А заполняется длинами ребер графа.

Как и любой базовый алгоритм, алгоритм Флойда - Уоршелла используется очень широко, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами. Но первое что приходит в голову конечно же транспортные сети.

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

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

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

Для заданного взвешенного графа G = (V, E) алгоритм находит кратчайшие пути из заданной вершины до всех остальных вершин. В, случае, когда в графе содержатся отрицательные циклы, достижимые из , алгоритм сообщает, что кратчайших путей не существует.

Matr[N][N] Matr[N][N] Matr[N][N]

1 0 inf 3 inf 2 0 inf inf inf 7 0 1 6 inf inf 0 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0

2 0 inf 1 2 inf 0 inf 5 1 inf 0 4 2 5 4 0 0 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0 0 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0

3 0 7 9 inf inf 14 7 0 10 15 inf inf 9 10 0 11 inf 2 inf 15 11 0 6 inf inf inf inf 6 0 9 14 inf 2 inf 9 0 0 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0 0 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0

4 0 inf -3 inf 2 0 inf inf inf 7 0 1 6 inf inf 0 0 4 -3 -2 2 0 -1 0 7 7 0 1 6 10 3 0 0 4 -3 -2 2 0 -1 0 7 7 0 1 6 10 3 0

5 0 inf -3 inf 2 0 inf inf inf 7 0 -1 -6 inf inf 0 В графе есть цикл отрицательного веса. В графе есть цикл отрицательного веса.

Протокол тестирования правильности работы программы по алгоритму Беллмана-Форда содержится в таблице 2. В входных данных вводится матрица расстояний, так же матрицу ожидаем получить и в выходных данных. Будем считать, что несуществующее ребро между двумя вершинами будет равняться inf = 1000. Первый пример характеризует ориентированный граф, второй же неориентированный. В 3 - м случае граф состоит из 6 вершин. В 4 и 5 примерах используются ребра отрицательного веса, где последний задает граф с циклом отрицательного веса.

Таблица 2 - Тестирование правильности алгоритма Беллмана-Форда

№ п/п Входные данные Выходные данные ТестMatr[N][N] Matr[N][N] Matr[N][N]

1 0 inf 3 inf 2 0 inf inf inf 7 0 1 6 inf inf 0 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0 0 10 3 4 2 0 5 6 7 7 0 1 6 16 9 0

2 0 inf 1 2 inf 0 inf 5 1 inf 0 4 2 5 4 0 0 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0 0 7 1 2 7 0 8 5 1 8 0 3 2 5 3 0

3 0 7 9 inf inf 14 7 0 10 15 inf inf 9 10 0 11 inf 2 inf 15 11 0 6 inf inf inf inf 6 0 9 14 inf 2 inf 9 0 0 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0 0 7 9 20 20 11 7 0 10 15 21 12 9 10 0 11 11 2 20 15 11 0 6 13 20 21 11 6 0 9 11 12 2 13 9 0

4 0 inf 3 inf -2 0 inf inf inf 7 0 -1 6 inf inf 0 0 10 3 2 -2 0 -1 0 5 7 0 -1 6 16 9 0 0 10 3 2 -2 0 -1 0 5 7 0 -1 6 16 9 0

5 0 inf -3 inf 2 0 inf inf inf 7 0 -1 -6 inf inf 0 В графе есть цикл отрицательного веса. В графе есть цикл отрицательного веса.

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

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

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

1 ГОСТ 7.32-2001. Отчет о научно-исследовательской работе. Структура и правила оформления [Текст]. - Взамен ГОСТ 7.32-91 ; введ. 2001-07-01. - Минск : Межгос. совет по стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. - 16 с. - (Система стандартов по информации, библиотечному и издательскому делу).

2 ГОСТ 7.1-2003. Библиографическая запись. Библиографическое описание. Общие требования и правила составления [Текст]. - Взамен ГОСТ 7.1-84, ГОСТ 7.16-79, ГОСТ 7.18-79, ГОСТ 7.34-81, ГОСТ 7.40-82 ; введ. 2004-07-01. - М. : Изд-во стандартов, 2004. - 116 с. - (Система стандартов по информации, библиотечному и издательскому делу).

3 Левитин А. В. Алгоритмы: ввдение в разработку и анализ. / А. В. Левитин ; пер. с англ. под общ. ред. С. Г. Тригуб. - М. : Издательский дом «Вильямс», 2006. - 576 с.

4 Макконелл Дж. Основы современных алгоритмов / Дж. Макконелл ; пер. с англ. под общ. ред. С. К. Ландо. - М. : Издательство ЗАО РИЦ «Техносфера», 2004. - 368 с.