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

Министерство образования и науки Российской Федерации

Казанский национально исследовательский технический университет

имени А. Н. Туполева

Кафедра Информационных технологий проектирования электронно-вычислительных средств

 

КУРСОВАЯ РАБОТА

по дисциплине

программирование на языке высокого уровня

по теме

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

 

 

 

ВЫПОЛНИЛ: студент группы 4114 Сайфутдияров К. Р.

ПРОВЕРИЛ: к. т. н. ассистент кафедры ИТП ЭВС Богула Н. Ю.

 

Оценка_______________

Подпись______________

______  __________ 2014 г.

 

 

 

Казань 2014

СОДЕРЖАНИЕ

1. Содержательная и формальная (математическая) постановка задачи
2. Разработка алгоритма решения задачи
3. Разработка структуры программы и алгоритмов программных модулей и их описание

 

4. Решение задачи на конкретном примере
5. Структура данных
6. Программная реализация алгоритма решения задачи и ее описание
7. Разработка системы тестов и отладка программы

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

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

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЯ

 

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

 — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.

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

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

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

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

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

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

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

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

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

 

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

                                  ,

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

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

 — это множество (упорядоченных) пар различных ребер, называемых дугами или ориентированными рёбрами.

Рис. 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. Описание переменных.

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