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

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

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

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

Кафедра теоретических основ компьютерной безопасности и криптографии

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

Кратчайшие пути в ориентированных графах

студента 2 курса 232 группы

Глыбина Дмитрия Александровича

Научный руководитель

доцент, к.ф.-м.н. А.В. Жаркова

• Содержание
• Введение
• 1. Необходимые определения
• 2. Кратчайшие пути в ориентированных графах
• 2.1 Алгоритм Дейкстры
• 2.2 Алгоритм Флойда-Варшалла
• 2.3 Алгоритм Беллмана-Форда
• 3. Программная реализация алгоритма Форда-Беллмана
• Заключение
• Список использованных источников
• Приложение А. Листинг программы

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

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

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

Приведем необходимые определения в соответствии с [1].

Неориентированным графом (или, для краткости, графом) называется пара

где - симметричное и антирефлексивное отношение на множестве вершин .

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

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

Рисунок 1 - Ориентированный граф.

Дуга с совпадающим началом и концом называется петлёй (см. рисунок 2).

Рисунок 2 - Ориентированный граф с петлёй.

Маршрутом в орграфе называется последовательность дуг , в которой для всех . Говорят, что маршрут проходит через вершины . Вершина называется его начальной вершиной, а - конечной.

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

Длиной маршрута называется количество составляющих его дуг.

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

Ориентированная сеть - орграф, дуги которого помечены положительными числами.

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

Кратчайший путь - путь, сумма весов дуг вдоль которого будет наименьшей. [1]

2. Кратчайшие пути в ориентированных графах

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

Существуют различные постановки задачи о кратчайшем пути:

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

· задача о кратчайшем пути между заданной парой вершин в орграфе. Требуется найти кратчайший путь из заданной вершины в заданную вершину орграфа;

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

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

В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе. [2]

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

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

Шаг 1. Положить и для всех вершин , отличных от . Окрасить вершину и положить .

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

Шаг 3. Если все вершины окрашены, т.е , - конец: для любой вершины кратчайший путь из в однозначно определятся, состоит из окрашенных дуг и имеет длину . Иначе перейти к шагу 2. [1]

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

ориентированный граф кратчайший путь

Таким образом, в алгоритме Дейкстры выполняется операций и алгоритм имеет время счёта порядка . [3]

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

Рисунок 3 - Сеть .

Приводимая таблица 1 заполняется по ходу выполнения алгоритма.

Таблица 1 - Работа алгоритма.

На первом этапе выставляются начальные значения для всех вершин , окрашивается вершина 1, дуги не окрашиваются. На втором этапе пересчитываются значения , выбирается вершина 2, имеющая наименьшее значение , она окрашивается и окрашивается дуга (1, 2), дающая значение . На третьем этапе, пересчитывая значения , выбираем вершину 3, для которой значение является наименьшим из рассматриваемых. Вершина 3 окрашивается и окрашивается дуга (2, 3). На четвертом этапе окрашивается вершина 4 и дуга (1, 4), так как длина этой дуги меньше, чем длина пути (1, 2, 3, 4). На пятом этапе окрашиваем вершину 6, для которой и соответствующая дуга (1, 6). На последнем этапе окрашивается вершина 5 и дуга (4, 5), дающая значение . Результатом работы алгоритма Дейкстры является орграф, представленный на рисунке 4.

Рисунок 4 - Орграф с окрашенными дугами.

Все вершины окрашены. В изображении графа окрашенные дуги выделены. Однозначно определенный путь из вершины 1 по окрашенным дугам в любую вершину будет кратчайшим.

2.2 Алгоритм Флойда-Варшалла

Алгоритм Флойда-Варшалла используется для нахождения в орграфе кратчайших путей между всеми парами вершин.

Примем следующие обозначения:

- длина кратчайшего пути из вершины в вершину , который в качестве промежуточных вершин может содержать только первые вершин графа. Если между вершинами и не существует ни одного пути, то будем считать, что ;

- матрица размера ( - количество вершин в данном орграфе), элемент которой совпадает с .

Шаг 1. Перенумеровать вершины исходного орграфа целыми числами от 1 до . Определить матрицу , задав величину каждого элемента равной длине кратчайшей дуги, соединяющей вершину с вершиной . Если в исходном орграфе указанные вершины не соединяются дугами, положить . Кроме того, для всех положить .

Шаг 2. Для целого , последовательно принимающего значения , определить по величинам элементов матрицы величины элементов матрицы , используя рекурсивное соотношение:

(1).

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

По окончании данной процедуры величина элемента матрицы определяет длину кратчайшего пути, ведущего из вершины в вершину .

Проанализируем вычислительную сложность алгоритма Флойда_Варшалла.

В алгоритме вычисляются матриц , каждая из которых состоит из элементов. Следовательно, в алгоритме Флойда-Варшалла необходимо вычислять элементов. Каждое такое вычисление осуществляется с помощью соотношения (1) и требует выполнения одной операции сложения и одной операции сравнения. Следовательно, в алгоритме Флойда-Варшалла выполняется сложений и сравнений. Общее число операций, выполняемых в алгоритме Флойда-Варшалла, пропорционально , т.е. алгоритм требует для своего выполнения времени счёта порядка . [3]

Пример - Алгоритм Флойда-Варшалла.

Рассмотрим работу алгоритма Флойда-Варшалла на примере орграфа, показанного на рисунке 5.

Рисунок 5 - Орграф.

Составим матрицу :

Величины элементов матрицы определяем следующим образом, используя формулу (1):

.

Используя формулу (1) продолжим вычисление матриц :

Кратчайшие пути для элементов матрицы :

Алгоритм Беллмана-Форда находит кратчайшие пути от одной вершины орграфа до всех остальных вершин. В отличие от алгоритма Дейкстры, алгоритм Форда-Беллмана допускает рёбра с отрицательным весом

Шаг 1. Положить и для всех вершин , отличных от . Окрасить вершину и положить .

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

Шаг 3. Если все вершины окрашены, т.е , и после выполнения шага 2 ни одно из чисел не меняется - конец алгоритма: для любой вершины кратчайший путь из в однозначно определяется, состоит из окрашенных дуг и имеет длину . Иначе перейти к шагу 2. [1; 3]

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

В разделе 2.1 была рассмотрена вычислительная сложность алгоритма Дейкстры, время счёта которого составляет , где - число вершин в орграфе. Так как в алгоритме Дейкстры каждая вершина окрашивается ровно один раз, а в алгоритме Беллмана-Форда она может окрашиваться до раза, то алгоритм Беллмана-Форда имеет время счёта порядка . [3]

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

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

Рисунок 6 - Орграф с дугами отрицательного веса.

Приводимая таблица 2 заполняется по ходу выполнения алгоритма.

Таблица 2 - Длины кратчайших дуг для данного орграфа.

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

Рисунок 7 - Окрашенный орграф с дугами отрицательного веса.

Все вершины окрашены. В изображении графа окрашенные дуги выделены. Однозначно определенный путь из вершины 1 по окрашенным дугам в любую вершину будет кратчайшим.

В результате проделанной работы была разработана и реализована программа поиска кратчайших путей от заданной вершины до всех остальных вершин данного ориентированного графа с помощью алгоритма Беллмана-Форда. Программа написана на языке C++ в среде Microsoft Visual C++ 2010. Код программы приведен в приложении А.

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

Рисунок 8 - Запуск программы.

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

Рисунок 9 - Ориентированный граф.

После ввода всех необходимых данных программа высчитывает кратчайшие пути от исследуемой вершины орграфа до всех остальных его вершин. На рисунке 10 представлен результат работы программы.

Рисунок 10 - Результат работы программы.

На рисунке 11 представлен результат работы программы с тем же графом, но для вершины под номером 2.

Рисунок 11 - Результат работы программы.

Проверим работу программы используя для исследования орграф с наличием дуг отрицательного веса (см. рисунок 12).

Рисунок 12 - Орграф с дугами отрицательного веса.

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

Рисунок 13 - Результат работы программы.

Заключение

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

Таким образом, все поставленные задачи были полностью решены.

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

1 Богомолов, А. М. Алгебраические основы теории дискретных систем [Электронный ресурс] / А. М. Богомолов, В. Н. Салий. М. : Наука. Физматлит, 1997. 368 с. Загл. с экрана. Яз. рус.

2 Нахождение кратчайшего пути в графе [Электронный ресурс] // Языки программирования [Электронный ресурс] URL : http://www.life_prog.ru/1_56629_nahozhdenie-kratchayshego-puti-v-grafe.html (дата обращения 29.05.2015). Загл. с экрана. Яз. рус.

3 Майника, Э. Алгоритмы оптимизации на сетях и графах [Электронный ресурс] / Э. Майника. Пер. с англ. М. : Мир, 1981. 323 с. Загл. с экрана. Яз рус.

Приложение А

#include <iostream>

#include <fstream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

const int INF = 1000000000;

int main(){

setlocale(LC_ALL, "Rus");

int n, m;

cout << "Введите число вершин в орграфе - ";

cout << endl << "От вершины " << s + 1 << ":" << endl;

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

if (i != s)

{

if(d[i] < INF/2)

{

cout << "кратчайший путь: " << endl;

for (int j = 0; j < path.size(); j++)

cout << path[j] + 1 << " ";

cout << endl;

}