Разработка и реализация алгоритма Флойда и Беллмана-Форда для поиска кратчайшего пути между всеми вершинами графа
Содержание
Введение
Разработка блок-схемы
алгоритмов
Разработка псевдокода
алгоритмов
Анализ трудоемкости
роста функции
Программа реализации
алгоритмов
Тестирование программ
реализации алгоритмов
.1 Тестирование
правильности
.2 Анализ по времени
Анализ результатов
Заключение
Список использованных
источников
Приложение А Код
программы по алгоритму Флойда
Приложение Б Код
программы по алгоритму Беллмана-Форда
Введение
Алгоритм Флойда поиска кратчайших
путей между всеми парами вершин.
Граф - это совокупность множества
вершин и множества пар вершин (связей между вершинами, дуг).
Алгоритм Флойда - Уоршелла -
алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного
графа без циклов с отрицательными весами с использованием метода динамического
программирования.
Этот алгоритм был
одновременно опубликован в статьях Роберта Флойда (Robert Floyd
<#"600184.files/image001.gif"> до
всех остальных вершин. В, случае, когда в графе содержатся отрицательные циклы, достижимые из ,
алгоритм сообщает, что кратчайших путей не существует.
1. Разработка блок-схемы алгоритмов
На рисунке 1 представлена
разработанная блок-схема алгоритма Флойда, где показано, каким образом,
работает этот алгоритм. i, j, k, - аргументы прохода по циклу, N - размер массива
расстояний, D[N][N] - массив расстояний.
Рисунок 1 - Блок-схема алгоритма
Флойда
На рисунке 2 представлена
разработанная блок-схема алгоритма Беллмана-Форда, где показано, каким образом,
работает этот алгоритм. Smej - матрица смежности графа, start_v - начальная вершина, mRast - массив существующих в
графе дуг, rez - массив кратчайших расстояний, RELAX(rez[mRast[j].to]) - улучшение пути между начальной и j-ой вершиной графа.
Рисунок 2 - Блок-схема алгоритма
Беллмана-Форда
2. Разработка псевдокода
Алгоритм Флойда.
На рисунке 3 приведена часть
псевдокода, где описан процесс ввода матрицы смежности заданного графа, где i,
j - аргументы порхода по циклу. Тут же зануляется главныя диогональ при
помощи условия - if(i==j), SizeMatr - размер матрицы(количество вешин в
графе).
Рисунок 3 - Ввод матрицы смежности
На рисунке 4 приведена часть
псевдокода, где описано вычисление матрицы кратчаших путей; будем улучшать путь
через k-ю вершину, если пойти из i в k, а из k в j
выгоднее, чем пойти напрямую из i в j, то запоминаем этот путь.
Рисунок 4 - Алгоритм Флойда
На рисунке 5 приведена часть
псевдокода, где описан вывод получившейся матрицы.
Рисунок 5 - Вывод матрицы
Алгоритм Беллмана-Форда.
На рисунке 6 приведена часть
псевдокода, где производится ввод n - количество вершин в графе, m - количество дуг в
графе, start_v - начальная вершина, Smej - матрица смежности графа G(n,m).
Рисунок 6 - Ввод матрицы смежности
На рисунке 7 приведена часть
псевдокода, где mRast - массив типа struct, в котором регистрируются from - начальная вершина
дуги, to - конечная вершина дуги
и length - длина этой дуги.
Рисунок 7 - Массив длинн
Ниже, на рисунке 8, заполняется
массив кратчайших путей до вершины i, изначально путь равен «бесконечности». Здесь бесконечность - это
некоторое значение, заведомо превосходящее все возможные расстояния. Длина дуги
к start_v приравнивается нулю.
Рисунок 8 - Заполнение массива
На рисунке 9 реализован,
непосредственно алгоритм Беллмана-Форда. Здесь rez[mRast[j].from] - длина пути из
начальной вершины до вершины, от которой начинается текущая дуга, mRast[j].length - длина текущей дуги, rez[mRast[j].to] - текущее кратчайшее
расстояние из start_v до j-ой вершины.
Рисунок 9 - Алгоритм Беллмана-Форда
В последней части псевдокода,
рисунок 10, осуществляется вывод кратчайших расстояний, при этом, в случае если
rez[i]=100000 путь до j-ой вершины не
определен.
Рисунок 10 - Вывод кратчайших
расстояний
3. Анализ трудоемкости роста функции
Время выполнения программы по
алгоритму Флойда состовляет O(n^3), так как в ней нет
практически ничего, кроме 3 вложенных друг в друга циклов.
Наилучшим случаем для алгоритма
станет граф в котором всего нет улучшения пути, т. е. вводимая матрица
расстояний не изменится после выполнения программы. В этом случае время
выполнения программы составит O(n^3).
Наихудшим случаем для алгоритма
станет граф с отрицательным циклом. Если в графе есть циклы отрицательного
веса, то формально алгоритм Флойда к такому графу неприменим. Но на самом деле
алгоритм корректно сработает для всех пар, пути между которыми никогда не
проходят через цикл негативной стоимости, а для остальных мы получим
какие-нибудь числа, возможно сильно отрицательные. Алгоритм можно научить
выводить для таких пар некое значение, соответствующее -∞.
В среднем случае алгоритм не будет
иметь отрицательных циклов и улучшит почти все пути. Таким образом он не
превысит an^3+bn^2+cn+d операций. алгоритм флойд беллман псевдокод
Анализ алгоритма Беллмана-Форда.
Время выполнения программы, имеет
порядок O(nm), где n - это количество вершин, а m - это количество дуг.
Наилучшим случаем для алгоритма
станет граф в котором 2 вершины и отсутствуют дуги, т. е. вводимая матрица
расстояний состоит из нулей.
4. Программа реализации алгоритмов
Ниже проиллюстрирована работа
алгоритма Флойда, а сам код написан в Приложении А. Заполнение матрицы
расстояний осуществляем при помощи чтения текстового файла «algF .txt», заполненная матрица
представлена на рисунке 11.
Рисунок 11 - Ввод матрицы из файла
На рисунке 12 представлен вывод
матрицы кратчайших расстояний заданного графа, помимо матрицы показано время
работы программы в секундах.
Рисунок 12 - Вывод результатов
работы программы по алгоритму Флойда
На рисунке 13 показана матрица
кратчайших путей, программа реализована с помощью алгоритма Беллмана-Форда.
Заполнение матрицы расстояний осуществляем при помощи чтения текстового файла «algBF .txt» В том же рисунке
показано время работы программы. Полный код программы находится в Приложении Б.
В реализации этого алгоритма пришлось добавить внешний цикл, в котором будут
пробегать все вершины: for(start_v=1;start_v<=n;start_v++),
таким образом этот алгоритм теперь находит не от одной вершины до всех
остальных, а от каждой вершины до всех остальных.
5. Тестирование программ реализации алгоритмов
.1 Тестирование правильности
Протокол тестирования правильности
работы программы по алгоритму Флойда содержится в таблице 1. В входных данных
вводится матрица расстояний, так же матрицу ожидаем получить и в выходных
данных. Будем считать, что несуществующее ребро между двумя вершинами будет
равняться inf = 1000. Первый пример характеризует ориентированный граф, второй
же неориентированный. В 3 - м случае граф состоит из 6 вершин. В 4 и 5 примерах
используются ребра отрицательного веса, где последний задает граф с циклом
отрицательного веса.
Таблица
1 - Тестирование правильности алгоритма Флойда
№ п/п
|
Входные данные
|
Выходные данные
|
Тест
|
|
|
Ожидаемый результат
|
Действительный результат
|
|
|
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
|
В графе есть цикл отрицательного веса.
|
В графе есть цикл отрицательного веса.
|
+
|
Проанализировав оба протокола мы
увидим, что обе программы работают корректно и выводят одно и тоже правильное
решение.
5.2 Анализ по времени
Анализ по времени проводится
функцией clock() из стандартной библиотеки <time.h>. Длины ребер задаем с помощью функции rand() из той же
библиотеки <time.h>, длины этих ребер будут
варьироваться от 0 до 99. Ниже на рисунке 14 представлена диаграмма роста
функции f(t)=N, где t - время работы программы в секундах, а N - количество вершин.
«Жирным» выделен график роста функции алгоритма Флойда, а «тонким» выделен
график роста функции алгоритма Беллмана-Форда.
Рисунок 14 - Диаграмма роста функции
f(t)=N
6. Анализ результатов
Проанализируем результаты, алгоритмы
Флойда и Беллмана-Форда очень похожи по своей структуре и поиску кратчайших
путей, они различаются по хранению промежуточной информации о кратчайших путях.
Исходя из этого, они различаются и в скорости роста функции f(t)=N. Как показали тесты,
эти два алгоритма схожи и в работе с ребрами отрицательного веса.
Заключение
Для достижения поставленной цели
потребовалось реализовать алгоритмы Флойда и Беллмана-Форда в среде (программе)
Microsoft Visual Studio. При создание кода программы использовалась программа Microsoft Visual Studio 2008. В результате при
помощи созданной программы была получена возможность нахождения минимального
расстояния между всеми вершинами, при случайном распределении длин ребер, при
ручном вводе и вводе при помощи файла. Так же был изменен код алгоритма
Беллмана-Форда, для того, чтобы этот алгоритм находил кратчайшие пути между
всеми вершинами графа, а не от одной вершины до всех остальных.
Проанализирована работа алгоритмов Флойда и Беллмана-Форда, после чего
составлены диаграммы тестирования скорости работы, по которым можно сравнить
работу алгоритмов.
Можно добавить, что поиск пути не
тривиальная задача, существует несколько хороших, надежных, и всем известных
алгоритмов, которые заслуживают должного внимания в сообществе разработчиков.
Помимо представленных выше алгоритмов, хорошо известны такие алгоритмы как
алгоритм Дейкстры, алгоритм Джонсона, все они решают одни и те же задачи, но
подходы к решению отличаются.
Некоторые алгоритмы поиска пути не
очень эффективны, но их изучение позволяет постепенно вводить концепции. Так
можно понять, как решаются различные проблемы.
Список использованных источников
1 ГОСТ 7.32-2001.
Отчёт о научно-исследовательской работе. Структура и правила оформления
[Текст]. - Взамен ГОСТ 7.32-91 ; введ. 2001-07-01. - Минск : Межгос. совет по
стандартизации, метрологии и сертификации ; М. : Изд-во стандартов, 2001. - 16
с. - (Система стандартов по информации, библиотечному и издательскому делу).
ГОСТ 7.1-2003.
Библиографическая запись. Библиографическое описание. Общие требования и
правила составления [Текст]. - Взамен ГОСТ 7.1-84, ГОСТ 7.16-79, ГОСТ 7.18-79,
ГОСТ 7.34-81, ГОСТ 7.40-82 ; введ. 2004-07-01. - М. : Изд-во стандартов, 2004.
- 116 с. - (Система стандартов по информации, библиотечному и издательскому
делу).
Левитин А. В.
Алгоритмы: ввдение в разработку и анализ. / А. В. Левитин ; пер. с англ. под
общ. ред. С. Г. Тригуб. - М. : Издательский дом «Вильямс», 2006. - 576 с.
Макконелл Дж.
Основы современных алгоритмов / Дж. Макконелл ; пер. с англ. под общ. ред. С.
К. Ландо. - М. : Издательство ЗАО РИЦ «Техносфера», 2004. - 368 с.
Приложение А
Код программы по алгоритму Флойда
#include
<iostream>
#include <stdio.h>
#include <fstream>
#include
<time.h>namespace std;main()
{*f =
fopen("algF.txt","r");int inf = 1000000;ch = 0;count = 0, i
= 0, N;loc("russian");::global(loc);_t t;=
clock();(time(NULL));(f,"%d",&N);**MatrS = new int *[N];(int i =
0; i < N; i++)
{[i] = new int[N];
}("\n%d\n",N);("Матрица
расстояний\n");(!feof(f))
{(int i=0;i<N;i++)
{(int j=0;j<N;j++)
{(f,"%d",&MatrS[i][j]);(i==j)[i][j]
= 0;("%d ",MatrS[i][j]);
}("\n");
}
}(f);(int k=0 ; k<N ;
k++)
{(int i=0 ; i<N ;
i++)
{(int j=0 ; j<N ;
j++)
{((MatrS[i][k] +
MatrS[k][j]) < MatrS[i][j])[i][j] = MatrS[i][k] + MatrS[k][j];
}
}
}(int i = 0; i < N;
i++)[] MatrS[i];[] MatrS;("Матрица кратчайших путей\n");(int i=0 ;
i<N ; i++)
{(int j=0 ; j<N ;
j++)
{("%d
",MatrS[i][j]);
}("\n");
}("Программе
потребовалось %.3f сек.\n",((float)t)/CLOCKS_PER_SEC);("pause");
}
Приложение Б
Код программы по
алгоритму Беллмана-Форда
#include <stdio.h>
#include <iostream>
#include <time.h>namespace
std;int inf=1E9;n,m,i,*rez,j,start_v,k=1;Duga
{from,to,length;
}*mRast;main()
{*f =
fopen("algBF.txt","r");loc("russian");::global(loc);(f,"%d
%d",&n,&m);_t t;=clock();**Smej=new int *[n];= new Duga [m];(i=1;
i<=n; i ++)
{[i]=new int [n];(j=1; j<=n; j++)
{(f,"%d",&Smej[i][j]);(Smej[i][j]!=0)
{[k].from=i;[k].to=j;[k].length=Smej[i][j];++;
}
}
}(int i = 0; i < N; i++)[]
Smej[i];[] Smej;(f);(start_v=1;start_v<=n;start_v++)
{=new int
[n];(i=1;i<=n;++i)[i]=inf;[start_v]=0;(i=1;i<=(n+1);i++)
{(j=1;j<=m;j++)
{(rez[mRast[j].from]<inf
&& rez[mRast[j].from]+mRast[j].length<rez[mRast[j].to])(i==(n+1))
{("В графе есть цикл
отрицательного веса");("pause");0;
}[mRast[j].to]=rez[mRast[j].from]+mRast[j].length;
}
}(i=1;i<=n;++i)
{(rez[i]==inf) printf("нет
пути\n"); else printf("%d ",rez[i]);
}("\n");
}=clock()-t;("Время работы
%f", (double)t/CLOCKS_PER_SEC);[] mRast;[] rez;("pause");
}