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

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

 

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

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМЕНИ Н.Г.ЧЕРНЫШЕВСКОГО»

 

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

 

 

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

 

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

 

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

специальности 090301 «Компьютерная безопасность»

факультета компьютерных наук и информационных технологий

Чабановой Дарьи Васильевны

 

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

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

                                                                  подпись, дата   

 

Зав. кафедрой

профессор, к.ф.-м.н.   _____________  В.Н. Салий

     подпись, дата      

 

 

Саратов 2013

 

СОДЕРЖАНИЕ

 

 

 

 

ВВЕДЕНИЕ

 

 

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

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

 

1 Необходимые определения

 

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

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

Графы используются в качестве функциональных моделей дискретных систем, при этом вершины соответствуют элементам системы, а дуги – связям между элементами. [1]

 

2 Алгоритмы нахождения  кратчайших путей в ориентированных  графах

 

 

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

 

Алгоритм Форда–Беллмана был впервые разработан в 1969 году. Этот алгоритм не очень быстр, но работает и на графах с отрицательными ребрами. Решим задачу по нахождению кратчайших путей в графе, в котором заведомо нет отрицательных циклов. [3]

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

Установим что,   равно 0 при , или в противном случае.

Теперь рассмотрим все пути из  в , содержащие ровно  рёбер. Каждый такой путь есть путь из  ребра, к которому добавлено последнее ребро. Если про пути длины  все данные уже подсчитаны, то определить -й столбец матрицы не составляет труда.[3]

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

for

do

 

for to

do for

if

then [3]

 

 

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

 Дан взвешенный ориентированный граф  , без петель и дуг отрицательного веса в соответствии с рисунком 1. Задача найти кратчайшие пути.   При завершении алгоритма мы получим массив содержащий кратчайшие пути. [4]

Рисунок 1 – Взвешенный ориентированный граф.

Составим матрицу смежности как показано в таблице 1.

Таблица 1 – Матрица смежности.

0	7	9	∞	∞	14
∞	0	10	15	∞	∞
∞	∞	0	11	∞	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Присвоим всем элементам массива значение . Перебираем все вершины согласно алгоритму.

; ;

; ;

; ;

; ;

; ;

; ;

В итоге получаем на выходе массив с следующими элементами:

; ; ; ; ; .

 

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

 

Этот алгоритм был разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом. Данный алгоритм находит кратчайшие расстояния между всеми парами вершин за . Описание алгоритма: вводим переменную равная кратчайшему пути из вершины до вершины , фиксируем вершину , затем перебираем всевозможные пары вершин и если , то делаем .[2]

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

 Дан взвешенный ориентированный граф  , без петель и дуг отрицательного веса в соответствии с рисунком 2. Задача найти кратчайшие пути. Так как в нашем примере 6 вершин на шестом шаге мы получим таблицу содержащую кратчайшие пути.[4]

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

Шаг 1. Составим матрицу смежности, фиксируем первую вершину и начнем работу алгоритма (см. таблица 2).

 

Таблица 2 – Шаг 1.

0	7	9	∞	∞	14
∞	0	10	15	∞	∞
∞	∞	0	11	∞	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Шаг 2. Фиксируем вторую вершину и продолжаем работу алгоритма (см. таблицу 3).

Таблица 3 – Шаг 2.

0	7	9	22	∞	14
∞	0	10	15	∞	∞
∞	∞	0	11	∞	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Шаг 3. Фиксируем третью вершину и продолжаем работу алгоритма (см. таблицу 4).

Таблица 4 – Шаг 3.

0	7	9	20	∞	11
∞	0	10	15	∞	12
∞	∞	0	11	∞	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Шаг 4. Фиксируем четвертую вершину и продолжаем работу алгоритма (см. таблицу 5).

 

Таблица 5 – Шаг 4.

0	7	9	20	∞	11
∞	0	10	15	21	12
∞	∞	0	11	17	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Шаг 5. Фиксируем пятую вершину и продолжаем работу алгоритма (см. таблицу 6).

Таблица 6 – Шаг 5.

0	7	9	20	∞	11
∞	0	10	15	21	12
∞	∞	0	11	17	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0

Шаг 6. Фиксируем шестую вершину и продолжаем работу алгоритма (см. таблицу 7).

Таблица 7 –Шаг 6.

0	7	9	20	23	14
∞	0	10	15	21	12
∞	∞	0	11	17	2
∞	∞	∞	0	6	∞
∞	∞	∞	∞	0	∞
∞	∞	∞	∞	9	0