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

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

21

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

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

1. Содержательная и формальная (математическая) постановка задачи

алгоритм программа отладка

Алгоритм Беллмана-Форда -- алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| Ч |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Граф, или неориентированный граф -- это упорядоченная пара, для которой выполнены следующие условия:

-- это непустое множество вершин или узлов;

-- это множество пар (в случае неориентированного графаРазмещено на http://www.allbest.ru/

21

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

-- неупорядоченных) вершин, называемых рёбрами.

Рис. 1.1. Неориентированный граф.

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

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

Вершины и называются концевыми вершинами (или просто концами) ребра . Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Два ребра называются кратными, если множества их концевых вершин совпадают.

Ребро называется петлёй, если его концы совпадают, то есть .

Степенью вершины называют количество инцидентных ей рёбер (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф (сокращённо орграф) -- это упорядоченная пара

,

для которой выполнены следующие условия:

-- это непустое множество вершин или узлов,

-- это множество (упорядоченных) пар различных ребер, называемыхРазмещено на http://www.allbest.ru/

21

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

дугами или ориентированными рёбрами.

Рис. 1.2. Ориентированный граф

Дуга -- это упорядоченная пара вершин , где вершину называют началом, а -- концом дуги. Можно сказать, что дуга ведёт от вершины к вершине .

Смешанный граф -- это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые -- неориентированными. Записывается упорядоченной тройкой

,

где , и определены так же, как выше.

Ориентированный и неориентированный графы являются частными случаями смешанного.

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

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

Ориентированным маршрутом (или путем) в орграфе называют конечную последовательность вершин и дуг, в которой каждый элемент инцидентен предыдущему и последующему.

Циклом называют цепь, в которой первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.

Всякий простой неэлементарный путь содержит элементарный цикл.

Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).

Петля -- элементарный цикл.

Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.

Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Таблица 1.1. Обозначение элементов

№	Обозначение элементов математической модели	Наименование элементов математической модели
1	G	Граф
2	V	непустое множество вершин или узлов
3	A	множество (упорядоченных) пар различных ребер

2. Разработка алгоритма решения задачи

Опишем алгоритм по шагам:

Шаг 0. Занумеруем все вершины из G=(V,E), так что V = {1, 2, ... p} и при этом номер «1» имеет именно та вершина, из которой будут найдены кратчайшие пути во все остальные вершины. Построим, далее матрицу

M = (mij ), i,j = 1, 2, ... p, положив

Шаг 1. Около первой строки матрицы M, слева от матрицы, поставим числовую пометку «0» и такую же пометку проставим над первым столбцом матрицы. Затем рассмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму проставим над столбцом, в котором эта клетка находится. Затем отразим пометки столбцов относительно главной диагонали. Возникнут помеченные строки. С каждой из помеченных строк проделаем то же самое: просмотрим помеченную строку слева направо и всякий раз, встречая клетку с числом, прибавим это число к пометке строки и сумму поставим в качестве пометки над столбцом, в котором эта клетка стоит. При этом будем соблюдать принцип: «имеющуюся пометку не менять». Затем пометки столбцов отразим относительно главной диагонали и с помеченными строками вновь проделаем то же самое. И так далее, пока не окажутся помеченными все строки и все столбцы.

Шаг 2. Просмотрим строки таблицы в порядке возрастания их номеров. В каждой строке просматриваются клетки слева направо и всякий раз, когда встречается число, оно складывается с пометкой строки и сумма сравнивается с пометкой столбца, в котором найденное число расположено. Если сумма оказалась меньше, чем пометка столбца, то эта пометка столбца заменяется на упомянутую сумму. Если же сумма оказалась больше или равной пометке, то ничего не меняется. После такого просмотра всех строк новые пометки столбцов отражаются относительно главной диагонали и вся процедура повторяется. И так до тех пор пока не прекратятся какие бы то ни было изменения в пометках.

Шаг 3. Теперь по пометкам можно построить кратчайшие пути из первой вершины во все остальные. Фиксируем произвольную вершину k (k = 2,3,...p) и опишем кратчайший путь из первой вершины в вершину k. Во-первых, длина этого кратчайшего пути равна пометке л k , стоящей над столбцом номер k. Во-вторых, предпоследняя вершина в кратчайшем пути из первой вершины в вершину k находится так: в столбце номер k отыскиваем число, сумма которого с пометкой строки, в которой оно расположено, равна л k. Пусть номер строки, в которой найденное число оказалось, равен l. Тогда предпоследней вершиной в кратчайшем пути из 1 в k будет вершина l. Вершину, которая предшествует вершине l, надо отыскивать как предпоследнюю в кратчайшем пути из 1 в l и так далее.

Таблица 2.1. Обозначение элементов.

№	Обозначение элементов математической модели	Наименование элементов математической модели
1	G	Граф
2	V	Количество вершин графа
3	E	Количество ребер графа

3. Разработка структуры программы и алгоритмов программных модулей и их описание

Структура программы

Структура программы показана на рис. 3.1.

1

Рис. 3.1. Модульная структура программы.

Сопряжения модулей

Сопряжение модулей программы описана в таблице 3.1.

Таблица 3.1. Сопряжение модулей.

Номер	Вход	Выход
1	int n, int s	-
2	-	bool

4. Решение задачи на конкретном примере

Рассмотрим на контрольном примере решение задачи с входным файлом “input.txt . В входном файле будут содержаться количество вершин в графе и матрица смежности. Бесконечность будет обозначаться 0.

Входной файл «input.txt» имеет вид:

8

0 10 13 0 0 0 0 0

10 0 0 0 0 0 11 0

13 0 0 17 10 0 0 0

0 0 17 0 0 16 12 0

0 0 10 0 0 11 0 15

0 0 0 16 11 0 15 10

0 11 0 12 0 15 0 0

0 0 0 0 15 10 0 0

1. Считываем количество вершин.

2. Считываем и проверяем веса ребер: если вес ребра больше 100000, или меньше -100000, или не цифра выводим ошибку, если равна 0 приписываем значение 100000 (бесконечность).

3. Вводим начальную вершину и проверяем: если меньше единицы, или больше количества вершин, или не цифра выводим ошибку и просим повторить ввод.

4. Проходим массив до тех пор, пока не найдем кратчайшие расстояния от начальной вершины:

Приведем пример. Пусть исходный взвешенный граф дает следующую матрицу M:

Начнем расставлять пометки:



Проведем уменьшение пометок:

5. Выводим кратчайшие пути

1>2: 10;

1>3: 13;

1>4: 30;

1>5: 23;

1>6: 34;

1>7: 21;

1>8: 38;

Структура данных

<Количество вершин>

<Веса ребер >

<Стартовая вершина >

Количество вершин не может превышать величины заданной программистом (в нашем случае 1000) и быть меньше 2.

Значение стартовой вершины не может превышать значения количества вершин и быть меньше нуля.

Описание массивов в программе приведено в таблице 5.1.

Таблица 5.1. Обозначения и описания массивов

№	Имя массива	Размерность массива	Описание массива
1	edge	Emax - Максимальное количество ребер в графе	Для хранения данных о ребрах
2	d	Vmax - максимальное количество вершин в графе.	Для хранения значений кратчайших путей

Описание переменных в программе приведено в таблице 5.2.

Таблица 5.2. Описание переменных.

№	Имя переменной	Тип переменной	Описание переменной
1	N	int	Количество вершин
2	Vmax	int	Размер массива или максимальное количество вершин
3	Emax	int	Максимальное количество ребер
4	u,v	int	Вершины ребра
5	success	bool	Используется при проверки правильности ввода
6	i,j	int	Счетчики
7	W	int	Вес ребра
8	E	Int	Количество ребер
9	Start	Int	Стартовая вершина
10	in, out	ifstrеam	Объекты для работы с файлами

5. Программная реализация алгоритма решения задачи и ее описание

В программной реализации алгоритма на Microsoft Visual Studio 2013 требуется включить следующие библиотеки:

"stdafx.h" - включаемый файл для стандартных системных включаемых файлов или включаемых файлов для конкретного проекта, которые часто используются, но не часто изменяются.

"iostream" - объектно-ориентированная иерархия классов, где используется и множественное, и виртуальное наследование. В ней реализована поддержка для файлового ввода/вывода данных встроенных типов.

В реализации программы также потребуются нижеперечисленные функции и методы:

cout - функция вывода в командную строку

cin - функция считывания из командной строки

cin.clear - функция очистки потока

_flushall - функция очистки буфера

good - функция проверки правильности ввода

Программная реализация алгоритма представлена в приложении A.

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

Тесты черного ящика

Для проектирования тестов программы методами черного ящика с помощью эквивалентного разбиения входных/выходных данных на области (классы) эквивалентности составлен список ситуаций, каждая из которых должна создаваться хотя бы одним тестом. Тестовые ситуации приведены в таблице 7.1, в скобках указаны их номера.

Таблица 7.1. Области входных/выходных данных тестов программы

Входные и выходные параметры	Допустимые значения	Недопустимые значения
Количество вершин, n	2…Vmax (1)	<2 (2), >Vmax (3), не цифра (4)
Вес ребра, w	-100000…1000000 (5)	Не цифра (6), <-100000 (7), >1000000 (8)
Стартовая вершина, start	0…n (9)	<1 (10), >n (11), не цифра (12)

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

Таблица 7.2. Тесты черного ящика для отладки программы

№ теста	Входные данные	Выходные данные	№ ситуаций
1	2 5 6 4 2 2	4 0	1, 5, 9
2	1001 5 3 6 …	Значение введено неверно. Повторите ввод	3, 5, 9
3	1 6 35 …	Значение введено неверно. Повторите ввод	2, 5, 9
4	G 6 4 …	Значение введено неверно. Повторите ввод	4, 5, 9
5	3 5 1000000000 …	Значение введено неверно. Повторите ввод	8, 1, 5, 9
6	5 6 -1000000000 …	Значение введено неверно. Повторите ввод	7, 1, 5, 9
7	9 4 f\ x …	Значение введено неверно. Повторите ввод	6, 1, 5, 9
8	2 6 3 5 8 3	Значение введено неверно. Повторите ввод	11, 1, 5, 9
9	2 6 3 5 8 0	Значение введено неверно. Повторите ввод	10, 1, 5, 9
10	2 6 3 5 8 0	Значение введено неверно. Повторите ввод	12, 1, 5, 9

Тесты белого ящика

Разработанные тесты методом белого ящика по критериям охвата основных путей выполнения алгоритма подпрограмм. В программе имеются составные условия. Поэтому использован критерий комбинаторного покрытия условий (см. таблицу 7.3).

Таблица 7.3. Комбинаторное покрытие условий тестами черного ящика

Из таблицы 7.3 видно, что тесты черного ящика обеспечивают полное комбинаторное покрытие всех ситуаций, поэтому нет необходимости в тестах белого ящика.

Заключение

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

Ниже следуют пункты, рассмотренные в курсовой работе.

1) Оформлялась содержательная часть задачи нахождения кратчайших расстояний графа.

2) Разрабатывалась алгоритм решения задачи.

3) Разрабатывались структуры программы и алгоритмы программных модулей.

4) Решил задачу на контрольном примере.

5) Разрабатывался и описывался граф.

6) Исходя из разработанного алгоритма, реализовалась программа.

7) Разрабатывались системы тестов в виде черных и белых ящиков.

Алгоритм был реализован еа языке высокого уровня С++. Отлаживалась программа в среде разработки Microsoft Visual studio 2013.

Курсовая работа выполнена в соответствии с требованиями в полном объеме.

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

1. Хохлов Д.Г. Основы технологии модульного программирования.

Учебное пособие - Казань: КГТУ (КАИ), 2003. 64 с.

2. Павловская Т.А. С/С++ Программирование на языке высокого уровня. Изд-во Питер, 2003. - 461 с.

3. Белицкий Я. Энциклопедия языка Си. М.: Мир, 1992.

4. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

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

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

7. Ананий В. Левитин Глава 8. Динамическое программирование:

Алгоритм Флойда поиска кратчайших путей между всеми парами вершин // Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. -- М.: Вильямс , 2006. -- С. 189--195, С. 349 -- 353.

8. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест,

Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. -- 2-е изд. -- М.: Вильямс, 2006. -- С. 1296.

7. https://ru.wikipedia.org

Приложение

Листинг программы

#include "stdafx.h"

#include <iostream>

#include "fstream"

#define inf 100000 //бесконечность

using namespace std;

// структура ребер

struct Edges{

int u,v,//вершины ребра

w;//вес ребра

};

const int Vmax = 1000; // Максимальное количество вершин

const int Emax = Vmax*(Vmax - 1) / 2; //Максимальное количестов ребер

int i, j,//счетчики

n,//количество вершин

e,//количество ребер

start; //стартовая вершина

Edges edge[Emax]; // создаем переменную типа Edges

int d[Vmax]; //массив в котором будут храниться наикратчайшие пути

bool success = false; // для проверки правильности ввода

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

void bellman_ford(int n, int s)

{

int i, j;

for (i = 0; i<n; i++) d[i] = inf;

d[s] = 0;

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

for (j = 0; j<e; j++)

if (d[edge[j].v] + edge[j].w<d[edge[j].u])

d[edge[j].u] = d[edge[j].v] + edge[j].w;

for (i = 0; i<n; i++) if (d[i] == inf)

cout << endl << start << "->" << i + 1 << "=" << "Нет";

else cout << endl << start << "->" << i + 1 << "=" << d[i];

}

//Функция ввода значений

bool vvod()

{

ifstream in("input.txt");

if (!in) {

cout << "Ошибка! Не удалось открыть файл\n";

return false;

}

int w;

in >> n;

if (!(in.good() && n<Vmax && n>1)) //проверка правильности ввода

{

cout << "Ошибка(1) чтения из файла!\n";

return false;

}

cout << "Количество вершин: " <<n <<endl;

e = 0;

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

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

{

in >> w;

if (!(in.good() && w<inf && w>-inf)) //проверка правильности ввода

{

cout << "Ошибка(2) чтения из файла!\n";

return false;

}

if (w != 0)

{

edge[e].v = i;

edge[e].u = j;

edge[e].w = w;

e++;

}

}

cout << "Стартовая вершина > ";

success = false;

while (!success) /*пока не введем верное значение*/

{

cin >> start;

if (cin.good() && start <= n && start >0) //проверка правильности ввода

{

success = true;

}

else

{

cout << "Значение введено неверно. Повторите ввод" << endl;

success = false;

}

cin.clear(); // очистка потока

_flushall();

}

return true;

}

//главная функция

void main()

{

setlocale(LC_ALL, "Rus");

if (!vvod()) goto end;

cout << "Список кратчайших путей:";

bellman_ford(n, start - 1);

end:

system("pause>>void");

Блок-Схема

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