Анализ алгоритмов нахождения кратчайших маршрутов в графе без отрицательных циклов: Дейкстры, Беллмана-Форда и Флойда-Уоршалла. Разработка интерфейса программы на языке C . Доказательство "правильности" работы алгоритма с помощью математической индукции.
Аннотация к работе
Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5. Присвоим 1-й вершине метку равную 0, потому как эта вершина - источник. Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещенную, и выбираем из еще не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. Здесь V - множество вершин графа G, E - множество его ребер, а w - весовая функция, заданная на ребрах графа (возвращает длину дуги ведущей из вершины v в u), d - массив, содержащий расстояния от вершины s до любой другой вершины.Алгоритм работает только для графов без ребер отрицательного веса. Алгоритм широко применяется в программировании и технологиях. Алгоритм Форда используется для решения той же задачи, если граф может содержать и ребра отрицательного веса. Алгоритм поиск Флойда используется для нахождения кратчайших расстояний между всеми парами вершин. Для выполнения данной курсовой работы была выбрана следующая система исходя из соображений простоты выполнения для разработчика и ясности структуры для пользователя.В данной курсовой работе рассмотрены три алгоритма для нахождения кратчайшего маршрута в графе, а именно алгоритма Дейкстры, алгоритма Форда, алгоритма Флойда. Была выполнена программная реализация данный алгоритмов на языке C . Разработанная программа предназначена для ознакомления пользователя с алгоритмами нахождения кратчайшего маршрута в графе.Рисунок А.1 - Выполнение алгоритма Дейкстры#include "stdafx.h" #include #include #include for (i=1;i<=n; i) for (j=0;j<m; j) if (t[edges[j].from]<inf && t[edges[j].from] edges[j].l<t[edges[j].to]) if (i==n) {printf("Не все кратчайшие пути определены, т.к. в графе есть циклы отрицательного веса"); return 0; } else t[edges[j].to]=t[edges[j].from] edges[j].
Введение
Целью данной работы является освоение основных алгоритмов нахождения кратчайшего маршрута в графе, а именно алгоритма Дейкстры, алгоритма Форда, алгоритма Флойда. В ходе курсовой работы будет разработана программная реализация данных алгоритмов.
Для работы с данной программой пользователь должен знать основы языка С , основы пользования ПК, теорию графов.
Пользователь сможет овладеть основными алгоритмами нахождения кратчайшего маршрута в графе, а именно алгоритма Дейкстры, алгоритма Форда, алгоритма Флойда.
1. Анализ алгоритмов нахождения кратчайших маршрутов
1.1 Алгоритм Дейкстры
Рассмотрим алгоритм Дейкстры [1].
Для примера возьмем такой ориентированный граф G:
Рисунок 1.1. - Граф G.
Этот граф мы можем представить в виде матрицы С:
Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5. Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере. Присвоим 1-й вершине метку равную 0, потому как эта вершина - источник. Остальным вершинам присвоим метки равные бесконечности.
Рисунок 1.2 - Присваивание вершине 1 метку 0.
Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.
Рисунок 1.3 - Назначение меток вершинам.
После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещенную, и выбираем из еще не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W. Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые еще не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.
Рисунок 1.4 - Нахождение более коротких маршрутов в вершины 3 и4.
Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, то-есть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины. Выполнив все действия получим такой результат:
Рисунок 1.5 - Результат выполнения алгоритма.
1.2 Алгоритм Форда
Алгоритм Беллмана-Форда - алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| ? |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает ребра с отрицательным весом.[3]
Алгоритм носит имя двух американских ученых: Ричарда Беллмана (Richard Bellman) и Лестера Форда (Lester Ford). Форд фактически изобрел этот алгоритм в 1956 г. при изучении другой математической задачи, подзадача которой свелась к поиску кратчайшего пути в графе, и Форд дал набросок решающего эту задачу алгоритма. Беллман в 1958 г. опубликовал статью, посвященную конкретно задаче нахождения кратчайшего пути, и в этой статье он четко сформулировал алгоритм в том виде, в котором он известен нам сейчас.
Формулировка задачи
Дан ориентированный или неориентированный граф G со взвешенными ребрами. Длиной пути назовем сумму весов ребер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины s до всех вершин графа.
Заметим, что кратчайших путей может не существовать. Так, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов ребер которого отрицательна, называется отрицательным циклом.
Решение задачи на графе без отрицательных циклов
Решим поставленную задачу на графе, в котором заведомо нет отрицательных циклов.
Для нахождения кратчайших путей от одной вершины до всех остальных, воспользуемся методом динамического прогриммирования. Построим матрицу Aij, элементы которой будут обозначать следующее: Aij - это длина кратчайшего пути из s в i, содержащего не более j ребер.
Путь, содержащий 0 ребер, существует только до вершины s. Таким образом, Ai0 равно 0 при i = s, и ? в противном случае.
Теперь рассмотрим все пути из s в i, содержащие ровно j ребер. Каждый такой путь есть путь из ребра, к которому добавлено последнее ребро. Если по пути длины все данные уже подсчитаны, то определить j-й столбец матрицы не составляет труда.
Так выглядит алгоритм поиска длин кратчайших путей в графе без отрицательных циклов: for do for to do for if then return
Здесь V - множество вершин графа G, E - множество его ребер, а w - весовая функция, заданная на ребрах графа (возвращает длину дуги ведущей из вершины v в u), d - массив, содержащий расстояния от вершины s до любой другой вершины.
Внешний цикл выполняется раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть.
Вместо массива d можно хранить всю матрицу A, но это требует O(V?) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длины. Для этого заведем матрицу Pij.
Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j ребер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).
Теперь алгоритм Беллмана-Форда выглядит так: for for to do for to do for if then
После выполнения этого алгоритма элементы содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так: while return p
Граф с отрицательными циклами
Алгоритм Беллмана-Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не , a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию: отслеживать изменения в графе и, как только они закончатся, сделать выход из цикла (дальнейшие итерации будут бессмысленны).
1.3 Алгоритм Флойда-Уоршалла
Алгоритм Флойда - Уоршелла - динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 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-й итерации для вычисления матрицы А применяется следующая формула: Ak[i,j]=min(Ak-1[i,j], Ak-1[i,k] Ak-1[k,j])
Нижний индекс k обозначает значение матрицы А после k-й итерации, но это не означает, что существует п различных матриц, этот индекс используется для сокращения записи. Для вычисления Ak[i, j] проводится сравнение величины Ak-i[i, j] (т.е. стоимость пути от вершины i к вершине j без участия вершины k или другой вершины с более высоким номером) с величиной Ak-1[i, k] Ak-1[k, j] (стоимость пути от вершины i до вершины k плюс стоимость пути от вершины k до вершины j). Если путь через вершину k дешевле, чем Ak-1[i, j], то величина Ak[i, j] изменяется [4].
Время выполнения этой программы, очевидно, имеет порядок 0(V3), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство "правильности" работы этого алгоритма также очевидно и выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого. алгоритм интерфейс программа индукция
Вывод
Алгоритм Дейксты находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса. Алгоритм широко применяется в программировании и технологиях.
Алгоритм Форда используется для решения той же задачи, если граф может содержать и ребра отрицательного веса.
Алгоритм поиск Флойда используется для нахождения кратчайших расстояний между всеми парами вершин.
2. Разработка нахождения системы нахождения кратчайших маршрутов
2.1 Разработка структуры системы
Для начала разработки системы нахождения кратчайших маршрутов необходимо определиться с структурой будущей системы. Для выполнения данной курсовой работы была выбрана следующая система исходя из соображений простоты выполнения для разработчика и ясности структуры для пользователя. Структура проектируемой системы приведена на рис.2.1.
Рисунок 2.1 - Структура проектируемой системы.
Для наглядности на рисунке 2.2 приведена диаграмма состояний.
Рисунок 2.2 - Диаграмма состояний.
2.2 Разработка интерфейса программы
Для реализации системы нахождения кратчайших маршрутов был выбран язык программирования C . Это связанно с следующими факторами: O в курсе обучения на нашей специальности этот язык является базовым для понимания принципов ООП;
O широко распространенный язык программирования: O позволяет легко реализовать поставленные задачи курсовой работы.
Для эффективного взаимодействия пользователя с системой необходимо организовать диалог, который должен быть: естественным, последовательным, не избыточным и понятным для пользователя. Процесс размещения информации на экране включает в себя следующее: 1. Решение какая информация будет выводиться на экран;
2. Определение основого формата этой информации;
3. Решение где она должна размещаться;
4. Разработка проекта размещения данной информации.
Для простаты понимания и реализации было принято решения выполнить интерфейс программы реализации алгоритмов выполнить в консоли. В начале программы пользователю предлагается выбрать один из рассматриваемых алгоритмов или выход из программы.
Структура интерфейса приведена на рис.1.
Рисунок 2.3 - Меню интерфейса программы.
2.3 Разработка программного модуля алгоритма Дейкстры
Для реализации алгоритма Дейкстры был разработан следующий программный код на языке C : cout<<"Значение начальной точки: ";
if(xn==xk) //Начальная и конечная точки
{ cout<<"Начальная и конечная точки совподают."<<endl;
2.4 Разработка программного модуля алгоритма Форда
Для реализации алгоритма Форда был разработан следующий программный код [2] на языке C : printf ("Введите номер стартовой вершины:");
scanf("%d",&v); -v;
for (i=0;i<n; i) t[i]=inf;
t[v]=0;
for (i=1;i<=n; i) for (j=0;j<m; j) if (t[edges[j].from]<inf && t[edges[j].from] edges[j].l<t[edges[j].to]) if (i==n) { printf("Не все кратчайшие пути определены, т.к. в графе есть циклы отрицательного веса"); return 0; } else t[edges[j].to]=t[edges[j].from] edges[j].l;
for (i=0;i<n; i)
{printf ("Вес кратчайшего пути от заданной вершины до вершины %d : ", i 1);
if (t[i]==inf) printf("до вершины дойти нельзя
"); else printf("%d
",t[i]);
} getch();
2.5 Разработка программного модуля алгоритма Флойда
Для реализации алгоритма Флойда был разработан следующий программный код [5] на языке C : for (k=0;k<n; k) for (i=0;i<n; i) for (j=0;j<n; j) if (d[i][k]<inf && d[k][j]<inf) d[i][j]=min(d[i][j],d[i][k] d[k][j]);
for (i=0;i<n; i) if (d[i][i]<0) { printf("INCORRECT INPUT"); return 0; } printf ("Матрица кратчайших путей графа:
");
for (i=0;i<n; i,printf("
")) for (j=0;j<n; j) if (d[i][j]==inf) printf("NO "); else printf("%d ",d[i][j]);
_getche();
3. Разработка инструкции пользователя
Для быстрого, однозначного и безошибочного использования разработанной программы необходимо разработать инструкцию пользователя.
При запуске программы загружается интерфейс программы с просьбой ввести номер алгоритма, который хотите рассмотреть. Меню содержит следующий текст: Выберите алгоритм, который хотите рассмотреть: [1] - алгоритм Дейкстры;
[2] - алгоритм Форда;
[3] - алгоритма Флойда;
[0] - для выхода из программы;
Пользователю необходимо ввести с клавиатуры номер алгоритма и нажать "Enter".
При выборе алгоритма Дейкстры пользователю необходимо ввести следующие исходные данные: O количество вершин графа;
O длинны ребер для каждого ребра;
O номер начальной вершины;
O номер конечной вершины.
В качестве результата будет выведен кратчайший маршрут из начальной в конечную вершину.
При выборе алгоритма Форда пользователю необходимо ввести следующие исходные данные: O количество вершин графа;
O количество ребер графа;
O записать через пробел для каждой вершины исходные данные в формате [X Y W], где дуга из вершины X в вершину Y имеет вес W;
O номер стартовой вершины.
В качестве результата будет выведен вес кратчайшего пути от заданной вершины до остальных.
При выборе алгоритма Флойда пользователю необходимо ввести следующие исходные данные: O количество вершин графа;
O вес каждого ребра
В качестве результата будет выведена матрица кратчайших путей графа.В данной курсовой работе рассмотрены три алгоритма для нахождения кратчайшего маршрута в графе, а именно алгоритма Дейкстры, алгоритма Форда, алгоритма Флойда. Была выполнена программная реализация данный алгоритмов на языке C . Интерфейс и вывод результатов производится в консоли.
Разработанная программа предназначена для ознакомления пользователя с алгоритмами нахождения кратчайшего маршрута в графе.
Перечень ссылок
1. Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе [электронный ресурс]
2. Алгоритм Форда-Беллмана (реализация на C ) [электронный ресурс]