Рассмотрение алгоритмов нахождения кратчайших путей в ориентированных графах. Описание и отличительные черты алгоритма Дейкстры, Флойда-Варшалла и Беллмана-Форда. Разработка и реализация программы для нахождения в заданном орграфе кратчайшего пути.
Аннотация к работе
Задача нахождения кратчайшего пути является жизненно необходимой задачей и используется она везде, начиная от поиска маршрута между объектами на местности и заканчивая навигационными системами.Неориентированным графом (или, для краткости, графом) называется пара где - симметричное и антирефлексивное отношение на множестве вершин . Под ориентированным графом (или, для краткости, орграфом) понимается пара , где - конечное непустое множество (вершины орграфа), а - отношение на множестве (пара называется дугой орграфа с началом и концом ). Отношение называют отношением смежности, а соответствующую ему двоичную булеву матрицу - матрицей смежности орграфа . Каждому орграфу можно сопоставить некоторое изображение - диаграмму, на которой вершины орграфа представляются точками (или кружками), а дуги - непрерывными кривыми (например, прямолинейными отрезками), ориентированными стрелкой от начальной вершины к конечной (см. рисунок 1). Дуга с совпадающим началом и концом называется петлей (см. рисунок 2).Существуют различные постановки задачи о кратчайшем пути: · задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения , который начинается в каждой из вершин орграфа (кроме ). Поменяв направление каждой принадлежащей орграфу дуге, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные); Требуется найти кратчайший путь из заданной вершины в заданную вершину орграфа;Будем считать, что в сети имеется вершина , из которой достижима любая другая вершина. Следующий алгоритм Дейкстры определяет кратчайший путь в орграфе из вершины в каждую вершину орграфа . Перед началом выполнения алгоритма все вершины и все дуги сети считаются не окрашенными. Окрасить одну из вершин , для которых величина является наименьшей, присоединить эту вершину к . Если все вершины окрашены, т.е , - конец: для любой вершины кратчайший путь из в однозначно определятся, состоит из окрашенных дуг и имеет длину .Алгоритм Флойда-Варшалла используется для нахождения в орграфе кратчайших путей между всеми парами вершин. Примем следующие обозначения: - длина кратчайшего пути из вершины в вершину , который в качестве промежуточных вершин может содержать только первые вершин графа. Если между вершинами и не существует ни одного пути, то будем считать, что ; Определить матрицу , задав величину каждого элемента равной длине кратчайшей дуги, соединяющей вершину с вершиной . По окончании данной процедуры величина элемента матрицы определяет длину кратчайшего пути, ведущего из вершины в вершину .Алгоритм Беллмана-Форда находит кратчайшие пути от одной вершины орграфа до всех остальных вершин. Окрасить одну из вершин , для которых величина является наименьшей, присоединить эту вершину к . Если все вершины окрашены, т.е , и после выполнения шага 2 ни одно из чисел не меняется - конец алгоритма: для любой вершины кратчайший путь из в однозначно определяется, состоит из окрашенных дуг и имеет длину . Так как в алгоритме Дейкстры каждая вершина окрашивается ровно один раз, а в алгоритме Беллмана-Форда она может окрашиваться до раза, то алгоритм Беллмана-Форда имеет время счета порядка . Рассмотрим работу алгоритма Беллмана-Форда на примере орграфа, представленного на рисунке 6, при этом найдем кратчайший путь из вершины 1 в каждую вершину данного орграфа.В данной курсовой работе были рассмотрены различные алгоритмы для поиска кратчайших путей в ориентированном графе, в результате чего была разработана и реализована программа для поиска кратчайших путей из данной вершины до всех остальных вершин данного орграфа в соответствии с алгоритмом Беллмана-Форда.
Задача нахождения кратчайшего пути является жизненно необходимой задачей и используется она везде, начиная от поиска маршрута между объектами на местности и заканчивая навигационными системами.
Чтобы решить поставленную задачу о нахождении кратчайшего пути необходимо перенести исследуемую систему на математический объект - ориентированный граф. Таким образом, задача сведется к нахождению кратчайшего пути между вершинами ориентированного графа.
Целью данной курсовой работы является рассмотрение различных алгоритмов нахождения кратчайших путей в ориентированных графах, в результате чего требуется разработать и реализовать программу для нахождения в заданном орграфе кратчайшего пути.
Вывод
В данной курсовой работе были рассмотрены различные алгоритмы для поиска кратчайших путей в ориентированном графе, в результате чего была разработана и реализована программа для поиска кратчайших путей из данной вершины до всех остальных вершин данного орграфа в соответствии с алгоритмом Беллмана-Форда.
Таким образом, все поставленные задачи были полностью решены.
Список литературы
1 Богомолов, А. М. Алгебраические основы теории дискретных систем [Электронный ресурс] / А. М. Богомолов, В. Н. Салий. М. : Наука. Физматлит, 1997. 368 с. Загл. с экрана. Яз. рус.
2 Нахождение кратчайшего пути в графе [Электронный ресурс] // Языки программирования [Электронный ресурс] URL : http://www.life-prog.ru/1_56629_nahozhdenie-kratchayshego-puti-v-grafe.html (дата обращения 29.05.2015). Загл. с экрана. Яз. рус.
3 Майника, Э. Алгоритмы оптимизации на сетях и графах [Электронный ресурс] / Э. Майника. Пер. с англ. М. : Мир, 1981. 323 с. Загл. с экрана. Яз рус.