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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ  
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ»

Кафедра математического моделирования бизнес-процессов 

 

 

 

КУРСОВАЯ РАБОТА 
по дисциплине «Программирование»

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

 

 

 

Выполнила:  
студентка гр. ИБ-19 
Чернова А.М.

Проверил: 
Швецов Я. П.

Новосибирск 2012

                                            Содержание:

1. Алгоритмы на графах…………………………………………..3

1.1 Основные определения  теории графов…………………….3

1.2 Машинное представление  графов………………………….4

2. Алгоритм Беллмана-Форда.  Описание………………………...7

3. Коды………………………………………………………………11

Список использованных источников……………………………..16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                          Алгоритмы на графах.

                       Основные определения теории графов

Графом называется пара , где V – некоторое множество, которое называют множеством вершин графа, а E – отношение на V ( ) - множество ребер графа. То есть все ребра из множества E соединяют некоторые пары точек из V.

Если отношение E симметричное (т.е. ), то граф называют неориентированным, в противном случае граф называют ориентированным. Фактически для каждого из ребер ориентированного графа указаны начало и конец, то есть пара (u, v) упорядочена, а в неориентированном графе (u, v) = (v, u).

Если в графе существует ребро (u, v), то говорят, что вершина v смежна с вершиной u (в ориентированном графе отношение смежности несимметрично).

Путем из вершины u в вершину v длиной k ребер называют последовательность ребер графа . Часто тот же путь обозначают последовательностью вершин . Если для данных вершин u, v существует путь из u в v, то говорят, что вершина v достижима из u. Путь называется простым, если все вершины в нем различны. Циклом называется путь, в котором начальная вершина совпадает с конечной. При этом циклы, отличающиеся лишь номером начальной точки, отождествляются.

Граф называется связанным, если для любой пары его вершин существует путь из одной вершины в другую.

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

При программировании вершины  графа обычно сопоставляют числам от 1 до N, где - количество вершин графа, и рассматривают . Ребра нумерую числами от 1 до M, где . Для хранения графа в программе можно применить различные методы. Самым простым является хранение матрицы смежности, т.е. двумерного массива, скажем A, где для невзвешенного графа (или 1), если и (или 0) в противном случае. Для взвешенного графа A[i][j] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j. Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N² значений, даже если ребер в графе существенно меньше, чем N². Это не позволяет построить алгоритм со временем порядка O(N) для графов, имеющих O(N) ребер.

Этого недостатка лишены такие  способы хранения графа, как одномерный массив длины N списков или множеств вершин. В таком массиве каждый элемент соответствует одной из вершин и содержит список или множество вершин, смежных ей.

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

Наконец, при решении задач  на графах, в том числе и с  помощью компьютера, часто используется его графическое представление. Вершины графа изображают на плоскости в виде точек или маленьких кружков, а ребра — в виде линий (не обязательно прямых), соединяющих соответствующие пары вершин, для неориентированного графа и стрелок – для ориентированного (если ребро направлено из u в v, то из точки, изображающей вершину u, проводят стрелку в вершину v).

Графы широко используются в различных областях науки и техники для моделирования отношений между объектами. Объекты соответствуют вершинам графа, а ребра — отношениям между объектами).

                      Машинное представление графов.

В теории графов классическим способом представления графа служит матрица инциденций. Это матрица A с n строками, соответствующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге _x, y_ ∈ E, содержит −1 в строке, соответствующей вершине x, 1 в строке, соответствующей вершине y, и нули во всех остальных строках (петлю, т.е. дугу вида _x, x_, удобно представлять иным значением в строке x, например, 2). В случае неориентированного графа столбец, соответствующий ребру {x, y}, содержит 1 в строках, соответствующих x и y, и нули в остальных строках. Это проиллюстрировано на рис. 2.1. С алгоритмической точки зрения матрица инциденций является, вероятно, самым худшим способом представления графа, который только можно себе представить. Во-первых, он требует mn ячеек памяти, причем большинство этих ячеек вообще занято нулями. Неудобен также доступ к информации. Ответ на элементарные вопросы типа «существует ли дуга _x, y_?», «к каким вершинам ведут ребра из x?» требует в худшем случае перебора всех столбцов матрицы, а следовательно, m шагов.

Лучшим способом представления  графа является матрица смежности, определяемая как матрица B = [bij] размера n × n, где bij= 1, если существует ребро, идущее из вершины x в вершину y, и bij= 0 в противном случае. Здесь мы подразумеваем, что ребро {x, y} неориентированного графа идет как от x к y, так и от y к x, так что матрица смежности такого графа всегда является симметричной. Это проиллюстрировано на рис. 2.2.

Основным преимуществом  матрицы смежности является тот  факт, что за один шаг можно получить ответ на вопрос «существует ли ребро из x в y?». Недостатком же является тот факт, что независимо от числа ребер объем занятой памяти составляет n². На практике это неудобство можно иногда уменьшить, храня целую строку (столбец) матрицы в одном машинном слове — это возможно для малых n.

Более экономным в отношении  памяти (особенно в случае неплотных графов, когда m гораздо меньше n²) является метод представления графа с помощью списка пар, соответствующих его ребрам. Пара _x, y_ соответствует дуге _x, y_, если граф ориентированный, и ребру {x, y} в случае неориентированного графа (рис. 2.3). Очевидно, что объем памяти в этом случае составляет 2m.Неудобством является большое число шагов — порядка m в худшем случае,— необходимое для получения множества вершин, к которым ведут ребра изданной вершины.

 

 

 

                Алгоритм Беллмана-Форда. Описание.

Алгоритм Беллмана-Форда применим также и к графам, содержащим рёбра отрицательного веса. Впрочем, если граф содержит отрицательный цикл, то, понятно, кратчайшего пути до некоторых вершин может не существовать (по причине того, что вес кратчайшего пути должен быть равен минус бесконечности); впрочем, этот алгоритм можно модифицировать, чтобы он сигнализировал о наличии цикла отрицательного веса, или даже выводил сам этот цикл.

Алгоритм носит имя  двух американских учёных: Ричарда  Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрёл этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвящённую конкретно задаче нахождения кратчайшего пути, и в этой статье он чётко сформулировал алгоритм в том виде, в котором он известен нам сейчас.

                                Описание алгоритма.

Допустим, что граф не содержит цикла отрицательного веса.

Заведён массив расстояний , который после отработки алгоритма будет содержать ответ на задачу. В начале работы он заполняется следующим образом: , а все остальные элементы равны бесконечности .

Сам алгоритм Беллмана-Форда представляет из себя несколько фаз. На каждой фазе просматриваются все рёбра графа, и алгоритм пытается произвести релаксацию (relax, ослабление) вдоль каждого ребра стоимости Релаксация вдоль ребра — это попытка улучшить значение значением . Фактически это значит, что мы пытаемся улучшить ответ для вершины , пользуясь ребром и текущим ответом для вершины .

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

 

                                          Реализация.

Для алгоритма Беллмана-Форда, в отличие от многих других графовых алгоритмов, более удобно представлять граф в виде одного списка всех рёбер (а не списков рёбер — рёбер из каждой вершины). В приведённой реализации (см. ч.3) заводится структура данных для ребра. Входными данными для алгоритма являются числа , список рёбер, и номер стартовой вершины . Все номера вершин нумеруются с по .

Простейшая реализация (см. ч.3).

Константа обозначает число "бесконечность" — её надо подобрать таким образом, чтобы она заведомо превосходила все возможные длины путей.

Проверка "if (d[e[j].a] < INF)" нужна, только если граф содержит рёбра отрицательного веса: без такой проверки бы происходили релаксации из вершин, до которых пути ещё не нашли, и появлялись бы некорректные расстояния вида , , и т.д.

Улучшенная реализация (см. ч.3).

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

С такой оптимизацией становится вообще ненужным ограничивать вручную  число фаз алгоритма числом — он сам остановится через нужное число фаз.

Восстановление путей (см. ч.3)

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

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

Алгоритм Беллмана-Форда работает по такой же логике: он, предполагая, что кратчайшее расстояние до одной вершины уже посчитано, пытается улучшить кратчайшее расстояние до другой вершины. Следовательно, в момент улучшения нам надо просто запоминать в , из какой вершины это улучшение произошло.

                             Доказательство алгоритма.

Во-первых, для недостижимых из вершин алгоритм отработает корректно: для них метка так и останется равной бесконечности (т.к. алгоритм Беллмана-Форда найдёт какие-то пути до всех достижимых из  вершин, а релаксация во всех остальных вершинах не произойдёт ни разу).

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

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

Доказательство. Рассмотрена произвольную вершину , до которой существует путь из стартовой вершины , и рассмотрим кратчайший путь до неё: . Перед первой фазой кратчайший путь до вершины найден корректно. Во время первой фазы ребро было просмотрено алгоритмом Форда-Беллмана, следовательно, расстояние до вершины было корректно посчитано после первой фазы. Повторяя эти утверждения раз, получается, что после -й фазы расстояние до вершины посчитано корректно, что и требовалось доказать.

Последнее, что надо заметить — это то, что любой кратчайший путь не может иметь более  ребра. Следовательно, алгоритму достаточно произвести только фазу. После этого ни одна релаксация гарантированно не может завершиться улучшением расстояния до какой-то вершины.

 

                          Случай отрицательного цикла.

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

Нетрудно понять, что алгоритм Форда-Беллмана сможет бесконечно делать релаксации среди всех вершин этого  цикла и вершин, достижимых из него. Следовательно, если не ограничивать число  фаз числом , то алгоритм будет работать бесконечно, постоянно улучшая расстояния до этих вершин.