Поиск кратчайших путей в графе методом Форда-Беллмана

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

 

 

 

 

 

 

Курсовая работа

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

Дискретная математика

 

 

 

на тему:

Поиск кратчайших путей в  графе методом Форда-Беллмана

 

 

 

 

 

 

 

 

 

 

 

       Выполнил: студент 2-го курса факультета ПМиИ Назаров Данис Николаевич                                              

                        Преподаватель: Труб Наталья Васильевна

 

 

 

 

 

 

 

2013 г.

Содержание

 

Введение…………………………………………………………………………...1

Основные  понятия………………………………………………………………...2

Методы решения  задачи…………………………………………………………..4

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

Разработка ПО……………………………………………………………………21

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

Заключение……………………………………………………………………….25

Список источников………………………………………………………………26

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Начало теории графов как  математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины 19-го столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул.

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

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

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

Существует много алгоритмов, решающих эту задачу: Дейкстры, Флойда-Уоршелла, Джонсона, Форда-Беллмана. В данной работе я рассматриваю некоторые из них, но основной целью работы является изучение алгоритма Форда-Беллмана и его программная реализация на языке программирования C#.

 

 

 

 

 

Основные понятия

Графом G называется совокупность 2-х множеств: V(точки) и E(линии), если между элементами этих 2-х множеств определено отношение инцидентности (соединения, связности), причем каждая линия e из множества E инцидентно ровно двум вершинам (точкам) v₁, v₂ из множества V. Линии называются ребрами графа, а точки – вершинами.

Если в графе каждому  ребру e приписано некоторое направление от одной из инцидентных вершин к другой, то такой граф называется ориентированным.

Множество ребер E может быть пустым. Такой граф называют нуль-графом.

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

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

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

Неориентированный граф без  кратных ребер и петель называется простым.

Смежными называются две вершины, соединенные ребром. При этом вершины инцидентны данному ребру, а ребро инцидентно вершинам.

Степенью вершины ρ(V) называется количество ребер, инцидентных данной вершине. Вершина степени 0 называется изолированной, а вершина степени 1 называется концевой.

Полным графом K_p называется такой граф, все вершины p которого смежные.

Два графа G₁ и G₂ называются изоморфными, если между вершинами этих графов существует биекция, при которой число ребер, соединяющих вершины V и U в графе G₁ равно числу ребер, соединяющих φ(V) и φ(U) в графе G₂. φ:V1→V2, сохраняющее число ребер, то есть (U,V) ϵ E₁ ↔ (φ(U), φ(V)) ϵ E₂.

Вес ребра — значение, поставленное в соответствие данному ребру взвешенного графа. Обычно, вес — вещественное число, в таком случае его можно интерпретировать как «длину» ребра.

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

Маршрут в графе — это чередующаяся последовательность вершин и рёбер  , в которой любые два соседних элемента инцидентны. Если  , то маршрут замкнут, иначе открыт.

Длина маршрута — количество рёбер в маршруте (с повторениями). Если маршрут  , то длина M равна k (обозначается  ).

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

Цикл — замкнутая цепь.

Связность. Две вершины в графе связаны, если существует соединяющая их (простая) цепь.

Связный граф — граф, в котором все вершины связаны.

Дерево — связный граф, не содержащий циклов.

Остовом (неориентированного) связного графа G=(V,E) называется его частичный граф S=(V,T), являющийся деревом.

Диаметр графа   — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.

Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.

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

 

 

Методы решения  задачи

Алгоритм Флойда-Уоршелла

Алгоритм Флойда - Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.

Более строгая формулировка этой задачи следующая:  
есть ориентированный граф G = (V, Е) каждой дуге v -> w этого графа сопоставлена неотрицательная стоимость C[v, w]. Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин v, w) любого пути от вершины v в вершины w, длина которого минимальна среди всех возможных путей от v к w.

Для определенности положим, что вершины графа последовательно  пронумерованы от 1 до n. Алгоритм Флойда использует матрицу А размера п * n, в которой вычисляются длины кратчайших путей. Вначале A[i, j] = C[i, j] для всех i != j. Если дуга i -» j отсутствует, то C[i, j] = infinity. Каждый диагональный элемент матрицы А равен 0.

Над матрицей А выполняется  п итераций. После k-й итерации A[i, j] содержит значение наименьшей длины путей из вершины i в вершину у, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и у могут находиться только вершины, номера которых меньше или равны k. На k-й итерации для вычисления матрицы А применяется следующая формула:  
A_k[i,j]=min(A_k-1[i,j], A_k-1[i,k]+A_k-1[k,j])

Нижний индекс k обозначает значение матрицы А после k-й итерации, но это не означает, что существует п различных матриц, этот индекс используется для сокращения записи. Для вычисления A_k[i, j] проводится сравнение величины A_k-i[i, j] (т.е. стоимость пути от вершины i к вершине j без участия вершины k или другой вершины с более высоким номером) с величиной A_k-1[i, k] + A_k-1[k, j] (стоимость пути от вершины i до вершины k плюс стоимость пути от вершины k до вершины j). Если путь через вершину k дешевле, чем A_k-1[i, j], то величина A_k[i, j] изменяется.

 

 

 

 

 

Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Формальное описание

 
В строке 1 производится обычная инициализация  величин d и pi, а в строке 2 инициализируется пустое множество вершин S. В этом алгоритме поддерживается инвариант, согласно которому в начале каждой итерации цикла while в строках 4-8 выполняется равенство Q = V — S. В строке 3 неубывающая очередь с приоритетами Q инициализируется таким образом, чтобы она содержала все вершины множества V; поскольку в этот момент S = 0, после выполнения строки 3 сформулированный выше инвариант выполняется. При каждой итерации цикла while в строках 4-8 вершина и извлекается из множества Q = V — S и добавляется в множество 5, в результате чего инвариант продолжает соблюдаться. (Во время первой итерации этого цикла u = s.) Таким образом, вершина и имеет минимальную оценку кратчайшего пути среди всех вершин множества V — 5. Затем строках 7-8 ослабляются все ребра (u, v), исходящие из вершины и. Если текущий кратчайший путь к вершине v может быть улучшен в результате прохождения через вершину и, выполняется ослабление и соответствующее обновление оценки величины d [v] и предшественника тг [v]. Обратите внимание, что после выполнения строки 3 вершины никогда не добавляются в множество Q и что каждая вершина извлекается из этого множества и добавляется в множество 5 ровно по одному разу, поэтому количество итераций цикла while в строках 4-8 равно | V|. Поскольку в алгоритме Дейкстры из множества V — S для помещения в множество 5 всегда выбирается самая "легкая" или "близкая" вершина, говорят, что этот алгоритм придерживается жадной стратегии.

 

 

 

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

 

Алгоритм Беллмана-Форда позволяет решить задачу о кратчайшем пути из одной вершины в общем случае, когда вес каждого из ребер может быть отрицательным. Для заданного взвешенного ориентированного графа G = (V, Е) с истоком s и весовой функцией w : Е —» R алгоритм Беллмана-Форда возвращает логическое значение, указывающее на то, содержится ли в графе цикл с отрицательным весом, достижимый из истока. Если такой цикл существует, в алгоритме указывается, что решения не существует. Если же таких циклов нет, алгоритм выдает кратчайшие пути и их вес.

1. Для начала заведем массив расстояний d[v], который будет содержать

расстояния до всех вершин в графе, d[s] приравняем к 0, для всех остальных вершин расстояние будем считать равным бесконечности.

 

2. Для каждой вершины, начиная с s, будем проводить сравнение (d[a]+c_b) c d[b], где a – рассматриваемая вершина, c_b – расстояние от вершины а до смежной вершины b, d[b] – текущее значение кратчайшего пути до b. Если (d[a]+cb) > d[b], то d[b] присваивает значение (d[a]+c_b), иначе d[b] остается неизменным. Сравнение проводится для каждой вершины, смежной вершине а. Всего необходимо сделать |V| — 1 проходов по всем ребрам графа. С каждым проходом величина d[v], представляющая собой оценку веса кратчайшего пути из истока s к каждой из вершин v є V, уменьшается до тех пор, пока она не станет равна фактическому весу кратчайшего пути из s в v.

 

3. После нахождения кратчайших путей нужно провести еще один проход по ребрам графа и если путь до какой-либо вершины x окажется короче d[x], то это означает, что в графе есть цикл с отрицательным весом.

 

Формальное описание

Bellman_Ford(G, w, s)

1    Initialize_Single_Source(G, s)

2    for i «- l to |V[G]|-1

3        do for (для) каждого ребра (u, v) є E[G]

4                        do RELAX(u,v,w)

5    for (для) каждого ребра (u, v) є E[G]

6            do if d[v] > d[u] + w(u, v)

7                     then return FALSE

8    return TRUE

 

После инициализации в  строке 1 всех значений d и R, алгоритм осуществляет |V| — 1 проходов по ребрам графа. Каждый проход соответствует одной итерации цикла for в строках 2-4 и состоит из однократного ослабления каждого ребра графа. После |V| — 1 проходов в строках 5-8 проверяется наличие цикла с отрицательным весом и возвращается соответствующее булево значение.