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

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

3

2

Содержание

• Введение
• 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) алгоритм находит кратчайшие пути из заданной вершины  до всех остальных вершин. В, случае, когда в графе  содержатся отрицательные циклы, достижимые из , алгоритм сообщает, что кратчайших путей не существует.

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++), таким образом этот алгоритм теперь находит не от одной вершины до всех остальных, а от каждой вершины до всех остальных.

Рисунок 13 - Вывод результатов работы программы по алгоритму Беллмана-Форда

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

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	0 inf -3 inf 2 0 inf inf inf 7 0 -1 -6 inf inf 0	В графе есть цикл отрицательного веса.	В графе есть цикл отрицательного веса.	+

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

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 с. - (Система стандартов по информации, библиотечному и издательскому делу).

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 с.

Приложение А

Код программы по алгоритму Флойда

#include <iostream>

#include <stdio.h>

#include <fstream>

#include <time.h>

using namespace std;

void main()

{

FILE *f = fopen("algF.txt","r");

const int inf = 1000000;

char ch = 0;

int count = 0, i = 0, N;

locale loc("russian");

locale::global(loc);

clock_t t;

t = clock();

srand(time(NULL));

fscanf(f,"%d",&N);

int **MatrS = new int *[N];

for(int i = 0; i < N; i++)

{

MatrS[i] = new int[N];

}

printf("\n%d\n",N);

printf("Матрица расстояний\n");

while(!feof(f))

{

for (int i=0;i<N;i++)

{

for (int j=0;j<N;j++)

{

fscanf(f,"%d",&MatrS[i][j]);

if(i==j)

MatrS[i][j] = 0;

printf("%d ",MatrS[i][j]);

}

printf("\n");

}

}

fclose(f);

for(int k=0 ; k<N ; k++)

{

for(int i=0 ; i<N ; i++)

{

for(int j=0 ; j<N ; j++)

{

if ((MatrS[i][k] + MatrS[k][j]) < MatrS[i][j])

MatrS[i][j] = MatrS[i][k] + MatrS[k][j];

}

}

}

for(int i = 0; i < N; i++)

delete [] MatrS[i];

delete [] MatrS;

printf("Матрица кратчайших путей\n");

for(int i=0 ; i<N ; i++)

{

for(int j=0 ; j<N ; j++)

{

printf("%d ",MatrS[i][j]);

}

printf("\n");

}

printf ("Программе потребовалось %.3f сек.\n",((float)t)/CLOCKS_PER_SEC);

system("pause");

}

Приложение Б

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

#include <stdio.h>

#include <iostream>

#include <time.h>

using namespace std;

const int inf=1E9;

int n,m,i,*rez,j,start_v,k=1;

struct Duga

{

int from,to,length;

}*mRast;

int main()

{

FILE *f = fopen("algBF.txt","r");

locale loc("russian");

locale::global(loc);

fscanf(f,"%d %d",&n,&m);

clock_t t;

t=clock();

int **Smej=new int *[n];

mRast= new Duga [m];

for (i=1; i<=n; i ++)

{

Smej[i]=new int [n];

for (j=1; j<=n; j++)

{

fscanf(f,"%d",&Smej[i][j]);

if (Smej[i][j]!=0)

{

mRast[k].from=i;

mRast[k].to=j;

mRast[k].length=Smej[i][j];

k++;

}

}

}

for(int i = 0; i < N; i++)

delete [] Smej[i];

delete [] Smej;

fclose(f);

for(start_v=1;start_v<=n;start_v++)

{

rez=new int [n];

for (i=1;i<=n;++i)

rez[i]=inf;

rez[start_v]=0;

for (i=1;i<=(n+1);i++)

{

for (j=1;j<=m;j++)

{

if (rez[mRast[j].from]<inf && rez[mRast[j].from]+mRast[j].length<rez[mRast[j].to])

if (i==(n+1))

{

printf("В графе есть цикл отрицательного веса");

system ("pause");

return 0;

}

else

rez[mRast[j].to]=rez[mRast[j].from]+mRast[j].length;

}

}

for (i=1;i<=n;++i)

{

if (rez[i]==inf) printf("нет пути\n"); else printf("%d ",rez[i]);

}

printf("\n");

}

t=clock()-t;

printf("Время работы %f", (double)t/CLOCKS_PER_SEC);

delete [] mRast;

delete [] rez;

system ("pause");

}

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