Разработка системы для нахождения кратчайших маршрутов

Введение

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

Для работы с данной программой пользователь должен знать основы языка С++, основы пользования ПК, теорию графов.

Пользователь сможет овладеть основными алгоритмами нахождения кратчайшего маршрута в графе, а именно алгоритма Дейкстры, алгоритма Форда, алгоритма Флойда.

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] изменяется.

Время выполнения этой программы, очевидно, имеет порядок 0(V3), поскольку в ней практически нет ничего, кроме вложенных друг в друга трех циклов. Доказательство «правильности» работы этого алгоритма также очевидно и выполняется с помощью математической индукции по k, показывая, что на k-й итерации вершина k включается в путь только тогда, когда новый путь короче старого.

алгоритм интерфейс программа индукция

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

Алгоритм Форда используется для решения той же задачи, если граф может содержать и рёбра отрицательного веса.

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

2. Разработка нахождения системы нахождения кратчайших маршрутов

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

Рисунок 2.1 — Структура проектируемой системы.

Для наглядности на рисунке 2.2 приведена диаграмма состояний.

Рисунок 2.2 — Диаграмма состояний.

2.2 Разработка интерфейса программы Для реализации системы нахождения кратчайших маршрутов был выбран язык программирования C++. Это связанно с следующими факторами:

Ш в курсе обучения на нашей специальности этот язык является базовым для понимания принципов ООП;

Ш широко распространённый язык программирования:

Ш позволяет легко реализовать поставленные задачи курсовой работы.

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

1. Решение какая информация будет выводиться на экран;

2. Определение основого формата этой информации;

3. Решение где она должна размещаться;

4. Разработка проекта размещения данной информации.

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

Структура интерфейса приведена на рис. 1.

Рисунок 2.3 — Меню интерфейса программы.

2.3 Разработка программного модуля алгоритма Дейкстры Для реализации алгоритма Дейкстры был разработан следующий программный код на языке C++:

cout<<" Значение начальной точки: «;

if (xn==xk) //Начальная и конечная точки

{

cout<<" Начальная и конечная точки совподают." <

getch ();

return 0;

}

for (i=0;i

{

flag[i]=0;

l[i]=65 535;

}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa (xn+1,s, 10);

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

{

strcpy (path[i]," X");

strcat (path[i], s);

}

do

{

for (i=0;i

if ((c[p][i]≠65 535)&&(!flag[i])&&(i≠p))

{

if (l[i]>l[p]+c[p][i])

{

itoa (i+1,s, 10);

strcpy (path[i+1], path[p+1]);

strcat (path[i+1]," -X");

strcat (path[i+1], s);

}

l[i]=minim (l[i], l[p]+c[p][i]);

}

p=min (n);

flag[p]=1;

}

2.4 Разработка программного модуля алгоритма Форда Для реализации алгоритма Форда был разработан следующий программный код на языке C++:

printf («Введите номер стартовой вершины:»);

scanf («%d» ,&v); —v;

for (i=0;i

t[v]=0;

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

for (j=0;j

if (t[edges[j]. from]

if (i==n) { printf («Не все кратчайшие пути определены, т.к. в графе есть циклы отрицательного веса»); return 0; } else

t[edges[j]. to]=t[edges[j].from]+edges[j].l;

for (i=0;i

{printf («Вес кратчайшего пути от заданной вершины до вершины %d: «, i+1);

if (t[i]==inf) printf («до вершины дойти нельзяn»); else printf («%dn», t[i]);

}

getch ();

2.5 Разработка программного модуля алгоритма Флойда Для реализации алгоритма Флойда был разработан следующий программный код на языке C++:

for (k=0;k

for (i=0;i

for (j=0;j

if (d[i][k]

for (i=0;i

if (d[i][i]<0) { printf («INCORRECT INPUT»); return 0; }

printf («Матрица кратчайших путей графа: n»);

for (i=0;i

for (j=0;j

if (d[i][j]==inf) printf («NO «); else printf («%d «, d[i][j]);

_getche ();

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

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

Выберите алгоритм, который хотите рассмотреть:

[1] - алгоритм Дейкстры;

[2] - алгоритм Форда;

[3] - алгоритма Флойда;

[0] - для выхода из программы;

Пользователю необходимо ввести с клавиатуры номер алгоритма и нажать «Enter» .

При выборе алгоритма Дейкстры пользователю необходимо ввести следующие исходные данные:

Ш количество вершин графа;

Ш длинны рёбер для каждого ребра;

Ш номер начальной вершины;

Ш номер конечной вершины.

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

При выборе алгоритма Форда пользователю необходимо ввести следующие исходные данные:

Ш количество вершин графа;

Ш количество рёбер графа;

Ш записать через пробел для каждой вершины исходные данные в формате [X Y W], где дуга из вершины X в вершину Y имеет вес W;

Ш номер стартовой вершины.

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

При выборе алгоритма Флойда пользователю необходимо ввести следующие исходные данные:

Ш количество вершин графа;

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

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

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

Перечень ссылок

1. Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе [электронный ресурс] http://habrahabr.ru/post/111 361

2. Алгоритм Форда-Беллмана (реализация на C++) [электронный ресурс] http://cybern.ru/algoritm-forda-bellmana-realizaciya-na-c.html

3. Алгоритм Беллмана — Форда [электронный ресурс] http://ru.wikipedia.org/wiki/Алгоритм_Беллмана-Форда

4. Алгоритм Флойда — Уоршелла [электронный ресурс] http://urban-sanjoo.narod.ru/floyd.html

5. Алгоритм Флойда-Уоршелла (реализация на C++) [электронный ресурс] http://cybern.ru/algoritm-flojda-uorshella-realizaciya-na-c.html

Приложение А. Экранные формы Рисунок А.1 — Выполнение алгоритма Дейкстры Рисунок А.2 — Выполнение алгоритма Форда Рисунок А.3 — Выполнение алгоритма Форда

Приложение Б. Листинг программы

#include «stdafx.h»

#include

#include

#include

#include

#include

#include

#include

#define word unsigned int

using namespace std;

#define WHITE 0

#define GREY 1

#define BLACK 2

int i, e, j, n, p, xn, xk;

int flag[11];

word c[11][11], l[11];

char s[80], path[80][11];

//****************Для алгоритма Форда*******************

const int inf=1E9;

int m, t[1000], h;

struct { int from, to, l; } edges[10 000];

// ****************** Для первого алгоритма************************

int min (int n)

{

int i, result;

for (i=0;i

if (!(flag[i])) result=i;

for (i=0;i

if ((l[result]>l[i])&&(!flag[i])) result=i;

return result;

}

word minim (word x, word y)

{

if (x

return y;

}

// ****************************ДЛЯ ТРЕТЬЕГО АЛГОРИТМА*******************

using namespace std;

int main ()

{setlocale (LC_ALL, «Russian»);

int alg;

while (1)

{printf («Выберите алгоритм, который хотите рассмотреть: n»);

printf («[1] - алгоритм Дейкстры; n»);

printf («[2] - алгоритм Форда; n»);

printf («[3] - алгоритма Флойда; n»);

printf («[0] - для выхода из программы; n»);

cin>>alg;

//Проверка

if (alg==0) break;

if (alg<0||alg>3)

{printf («Не верный ввод номера алгоритма nn»);

continue;

}

switch (alg)

{

case 1:

{cout<<" Введите число точек: «;

cin>>n;

for (i=0;i

for (j=0;j

for (i=0;i

for (j=i+1;j

{

cout<<" Задайте длинны рёбер от x" <<<" до x" <<<": «;

cin>>c[i][j];

}

cout<<" «;

for (i=0;i<<" X" <

cout<

for (i=0;i

{

printf («X%d», i+1);

for (j=0;j

{

printf («%6d», c[i][j]);

c[j][i]=c[i][j];

}

printf («nn»);

}

for (i=0;i

for (j=0;j

if (c[i][j]==0) c[i][j]=65 535; //nekonecno

cout<<" Значение начальной точки: «;

cin>>xn;

cout<<" Значение конечной точки: «;

cin>>xk;

xk—;

xn—;

if (xn==xk)

{

cout<<" Начальная и конечная точки совподают." <

getch ();

return 0;

}

for (i=0;i

{

flag[i]=0;

l[i]=65 535;

}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa (xn+1,s, 10);

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

{

strcpy (path[i]," X");

strcat (path[i], s);

}

do

{

for (i=0;i

if ((c[p][i]≠65 535)&&(!flag[i])&&(i≠p))

{

if (l[i]>l[p]+c[p][i])

{

itoa (i+1,s, 10);

strcpy (path[i+1], path[p+1]);

strcat (path[i+1]," -X");

strcat (path[i+1], s);

}

l[i]=minim (l[i], l[p]+c[p][i]);

}

p=min (n);

flag[p]=1;

}

while (p≠xk);

if (l[p]≠65 535)

{

cout<<" Путь: «<<

cout<<" Длинна пути: «<<

}

else

cout<<" Путь не существует!" <

_getche ();

}

break;

case 2:

{printf («Введите количество вершин графа:»);

scanf («%d» ,&n);

printf («Введите количество рёбер графа:»);

scanf («%d» ,&m);

for (i=0;i

{printf («Запишите через пробел для вершины %d», i+1);

printf («исходные данные в формате [X Y W], n»);

printf («где дуга из вершины X в вершину Y имеет вес W:»);

scanf («%d%d%d» ,&edges[i]. from,&edges[i].to,&edges[i].l);

—edges[i].from; —edges[i]. to;

if (edges[i]. from>n||edges[i].to>n)

{printf («Не верно введён номер вершины»);

getch ();

return 0;

}

}

printf («Введите номер стартовой вершины:»);

scanf («%d» ,&h); —h;

for (i=0;i

t[h]=0;

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

for (j=0;j

if (t[edges[j]. from]

if (i==n) { printf («Не все кратчайшие пути определены, т.к. в графе есть циклы отрицательного веса»); return 0; }

else t[edges[j]. to]=t[edges[j].from]+edges[j].l;

for (i=0;i

{printf («Вес кратчайшего пути от заданной вершины до вершины %d: «, i+1);

if (t[i]==inf) printf («до вершины дойти нельзяn»); else printf («%dn», t[i]);

}

_getche ();

}

break;

case 3:

{int n, i, j, k, d[100][100];

printf («Введите количество вершин графа:»);

scanf («%d» ,&n);

for (i=0;i

for (j=0;j

{printf («Введите вес ребера графа D [%d,%d]: «, i+1,j+1);

scanf («%d» ,&d[i][j]);

if (i==j) d[i][j]=min (d[i][j], 0);

if (d[i][j]==1001) d[i][j]=inf;

}

for (k=0;k

for (i=0;i

for (j=0;j

if (d[i][k]

for (i=0;i

if (d[i][i]<0) { printf («INCORRECT INPUT»); return 0; }

printf («Матрица кратчайших путей графа: n»);

for (i=0;i

for (j=0;j

if (d[i][j]==inf) printf («NO «); else printf («%d «, d[i][j]);

_getche ();

}

break;

}

}

return 0;

}