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

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

 

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

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

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

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

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

 

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

 

 

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

 

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

 

студентки 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

 

 

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

 

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

1. положить для всех вершин (кроме исходной) расстояние равное бесконечности, для исходной присвоить нулю;
2. выбрать непомеченную вершину , с минимальным расстоянием. Если такой вершины нет, то завершить работу;
3. пометить вершину ;
4. для всех непомеченных вершин, смежных с вершиной , попытаться уменьшить расстояние;
5. вернуться к шагу 2; [2]

Пример – Алгоритм Дейкстра.

Дан взвешенный ориентированный граф  , без петель и дуг отрицательного веса в соответствии с рисунком 3. Найти кратчайшие пути от некоторой вершины  графа  до всех остальных вершин этого графа. [4]

Рисунок 3 – Граф.

Каждой вершине из  сопоставим метку – минимальное известное расстояние от этой вершины до . Алгоритм работает пошагово – на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Шаг 1. Метка самой вершины  полагается равной 0, метки остальных вершин – бесконечности. Это отражает то, что расстояния от  до других вершин пока неизвестны. Все вершины графа помечаются как не посещённые.

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

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

Рисунок 4 –Пример графа.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» – длина пути. Рядом с каждой вершиной обозначена метка – длина кратчайшего пути в эту вершину из вершины 1(см. рисунок 5).

Рисунок 5 – Метки вершин.

Шаг 3. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6 согласно рисунку 6.

Рисунок 6 – Соседи вершины 1.

Шаг 4. Первый по очереди сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна согласно рисунку 7. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Рисунок 7 – Вершина 2.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины – 3-й как показано на рисунке 7 и 6-й согласно рисунку 8.

Рисунок 8 – Действия с соседями.

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

Рисунок 9 – Вычеркивание вершины 1.

Шаг 5. Снова находим «ближайшую» из не посещенных вершин. Это вершина 2 с меткой 7 как указано на рисунке 10.

Рисунок 10 – Помечаем вершину 2.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 – вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 – вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется рисунок 11.

Рисунок 11 – Изменение текущей метки.

 
Ещё один сосед вершины 2 – вершина 4 (см. рисунок 12). Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть . Поскольку , устанавливаем метку вершины 4 равной 22.

Рисунок 12 – Метка вершины 4.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную (см. рисунок 13).

Рисунок 13 – Посещенная вершина 2.

Повторяем алгоритм, выбрав вершину 3 рисунок 14. После её «обработки» получим такие результаты (см. рисунок 15):

Рисунок 14 – Вершина 3.

Дальнейшие шаги рисунок 15. Повторяем алгоритм для оставшихся вершин (см. рисунок 16).

Рисунок 15 – Посещенная вершина 3.

Рисунок 16 – Повторение алгоритма.

Рисунок 17 – Завершение алгоритма.

Завершение выполнения алгоритма (см. рисунок 17). Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины (см.рисунок 17). В данном примере все вершины зачеркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться не зачеркнутыми, если до них нельзя добраться. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й – 9, до 4-й – 20, до 5-й – 20, до 6-й – 11.

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

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

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

 

3 Программная реализация алгоритма Дейкстры

 

 

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

Рисунок 18 – Введите вершины.

Далее требуется ввести матрицу смежности графа (см. рисунок 19).

Рисунок 19 – Введите матрицу смежности.

Введите начальную вершину, из которой требуется найти кратчайший путь (см. рисунок 20).

Рисунок 20 – Введите начальную вершину графа.

Далее на экран выводится кратчайшие пути от заданной начальной вершины до всех остальных вершин (см. рисунок 21).

Рисунок 21 – Вывод результата.

В случае отсутствия решения или некорректно введенных данных, программа выдаст сообщение: «Маршрут недоступен» (см. рисунок 22).

Рисунок 22 – Ошибка.

 

ЗАКЛЮЧЕНИЕ

 

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

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

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

 

1. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука. Физматлит, 1997. – 368 с. – ISBN 5-02-015033-9.
2. Лекции по теории графов / Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. – М.: Наука. Гл. ред. физ.- мат. лит., 1990. – 384 с. – ISBN 5-02-013992-0.
3. Томас Х. Кормен., Чарльз И. Лейзерсон., Алгоритмы: построение и анализ. Учебное пособие, 2-е изд., — М.: Вильямс, 2006. —1296 с. — ISBN 0-07-013151-1
4. Алгоритм Дейкстра [Электронный ресурс] // Википедия свободная энциклопедия [Электронный ресурс] : полнотекстовая ВСЭ с картинками. URL: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры (дата обращения: 12.05.2013). Загл. с экрана. Яз.рус

 

Приложение А.

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

 

#include <cmath>

#include<clocale>

#include <iostream>

using namespace std;

const int V=100;

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

void Dijkstra(int GR[V][V], int st,int n)

{

int distance[V], count, index, i, u, m=st+1;

bool visited[V];

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

{

distance[i]=INT_MAX; visited[i]=false;

}

distance[st]=0;

for (count=0; count<n-1; count++)

{

int min=INT_MAX;

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

if (!visited[i] && distance[i]<=min)

{

min=distance[i]; index=i;

}

u=index;

visited[u]=true;

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

if (!visited[i] && GR[u][i] && distance[u]!=INT_MAX &&

distance[u]+GR[u][i]<distance[i])

distance[i]=distance[u]+GR[u][i];

}

cout<<"Стоимость пути из начальной вершины до остальных:\t\n";

for (i=0; i<n; i++) if (distance[i]!=INT_MAX)

cout<<m<<" > "<<i+1<<" = "<<distance[i]<<endl;

else cout<<m<<" > "<<i+1<<" = "<<"маршрут недоступен"<<endl;

}

//главная функция

void main()

{

setlocale(LC_ALL, "Rus");

int start; int GR[V][V]; int n; cin>>n;

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

for(int j=0; j<n;j++){

cin>>GR[i][j];}}

 

cout<<"Начальная вершина >> "; cin>>start;

Dijkstra(GR, start-1,n);

system("pause>>void");}