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

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Содержание

  • Введение
  • 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]=100 000 путь до j-ой вершины не определен.

Рисунок 10 — Вывод кратчайших расстояний

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

Время выполнения программы по алгоритму Флойда состовляет O(n^3), так как в ней нет практически ничего, кроме 3 вложенных друг в друга циклов.

Наилучшим случаем для алгоритма станет граф в котором всего нет улучшения пути, т. е. вводимая матрица расстояний не изменится после выполнения программы. В этом случае время выполнения программы составит O(n3).

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

В среднем случае алгоритм не будет иметь отрицательных циклов и улучшит почти все пути. Таким образом он не превысит an3+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 = 1 000 000;

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%dn», 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»);

}

ПоказатьСвернуть
Заполнить форму текущей работой