Разработка программного обеспечения для реализации алгоритма Дейкстры

Департамент образования города Нижний Новгород Государственное образовательное учреждение высшего профессионального образования НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. Р. Е. Алексеева КУРСОВАЯ РАБОТА Тема работы: «Разработка программного обеспечения для реализации алгоритма Дейкстры»

по предмету «Методы оптимизации»

Выполнил: Шамов Андрей Евгеньевич, группа 25-ВМ г. Нижний Новгород — 2010 г

1. Постановка задачи

2. Введение

3. Теоретическая часть

3.1 Общие сведения о графах

3.2 Описание принципа работы алгоритма

3.3 Пример выполнения алгоритма Дейкстра

4. Реализация программного обеспечения

4.1 Алгоритм для программной реализации задачи

4.2 Среда разработки программного обеспечения

5. Описание работы программы

5.1 Примеры работы программы

5.2 Обработка ошибок Заключение Список используемых ресурсов и литературы Приложение (код программы)

ПОСТАНОВКА ЗАДАЧИ алгоритм дейкстра программный граф Задачей данного курсового проекта является разработка программного обеспечения для реализации алгоритма, позволяющего находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса (алгоритма Дейкстры).

ВВЕДЕНИЕ

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

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

Если в графе используются ребра с отрицательным весом, тогда необходимо использовать другие алгоритмы, например Алгоритм Беллмана — Форда.

3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

3.1 ОБЩИЕ СВЕДЕНЬЯ О ГРАФАХ Для реализации алгоритма необходимо использовать граф. В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (пример на рис. 1).

рис. 1

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

3.2 ОПИСАНИЕ ПРИНЦИПА РАБОТЫ АЛГОРИТМА алгоритм дейкстра кратчайший граф Алгоритм Дейкстры ищет кратчайшие маршруты, идущие из первой вершины графа к остальным вершинам этого графа.

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

Сначала помечается первая вершина. Следующей, будет помечена вершина, ближайшая к исходной, и смежная с ней.

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

Рассмотрим все дуги, ведущие из помеченных вершин в одну непомеченную. Каждая такая дуга является последней дугой на пути из исходной вершины в эту непомеченную.

Выберем из этих путей кратчайший. А затем выберем среди них самый короткий ко всем непомеченным вершинам, и пометим вершину, к которой он ведет.

Алгоритм завершится, когда будут помечены все достижимые вершины.

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

3.3 ПРИМЕР ВЫПОЛНЕНИЯ АЛГОРИТМА ДЕЙКСТРА Пример выполнения алгоритма для графа, показанного на рисунке 2. Пусть требуется найти расстояния от 1-й вершины до всех остальных. Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Рис. 2

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

Рис. 3

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й (рис. 3). На этом этапе все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг: операция первого шага алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7. Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

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

Рис. 4

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

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

Рис. 5

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

Рис. 6

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Рис. 7

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

4. РЕАЛИЗАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ Для программной реализации алгоритма задача была формализована в виде алгоритма.

Для обозначения были использованы следующие переменные:

Таблица 1

4.1 АЛГОРИТМ ДЛЯ ПРОГРАММНОЙ РЕАЛИЗАЦИИ ЗАДАЧИ схема 1

На схеме 1 изображена блок-схема работы программы. Блок обрабатывающий алгоритм Дейкстры называется «Алгоритм Дейкстры» (к.о.) Его подробный алгоритм представлен ниже, на схеме 2.

Схема 2

При запуске программы на экран выводится запрос о вводе весов рёбер исследуемого графа. Данные, введённые пользователем, отображаются в виде матрицы смежности, в которой не существующие рёбра обозначаются нулями. После указанным рёбрам присваивается значение 2 147 483 647 (как максимальное значение 32-х битной переменной int), которое условно принимается за бесконечность.

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

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

Кроме стандартных функций из библиотек были использованы также следующие функции:

word minim (word x, word y) — функция, которая возвращает минимальное из x и y.

схема 3

int min (int n) — функция, которая возвращает номер элемента массива l[i] минимальной «неотмеченной» длиной пути (flag[i]=0).

схема 4

4.2 СРЕДА РАЗРАБОТКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ В качестве среды для разработки программного обеспечения была выбрана Microsoft Visual Studio Express 2008, средства Visual C++. Microsoft Visual Studio Express — линейка бесплатных интегрированных сред разработки, облегчённая версия Microsoft Visual Studio, разработанной компанией Microsoft.

Изначально в пакет входит компилятор, сама среда разработки, сходная по функциям c Microsoft Visual Studio, но ограниченная в них, и набор стандартных библиотек c/c++ - stdlib, STL. В пакет не входит Platform SDK для разработки приложений под Windows, но данный Platform SDK можно скачать с официального сайта Microsoft (где подробно описан процесс установки Platform SDK, настройка Visual C++ 2008 Express Edition для создания нового проекта под Windows (Wizard)).

Сама программа для реализации алгоритма Дейкстры создавалась как консольное приложение Win32.

5. ОПИСАНИЕ РАБОТЫ ПРОГРАММЫ Программа имеет консольный текстовый интерфейс. После запуска программы появится окно с инструкциями ввода информации для определения графа (отображение реализовано через матрицу смежности). После выполнения программа создает текстовый файл dalg. txt, в который добавляет результат выполнения после каждого задания (включая неудачные).

Для вычисления пути согласно алгоритму необходимо ввести:

Имя задания (либо текущую дату). Имя может быть произвольным, и присваивается каждому заданию.

Количество вершин графа (максимум 1000).

Расстояние между вершинами графа (максимум 2 147 483 647).

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

Примечание: если во время ввода были использованы большие параметры веса ребер, либо большое количество вершин, выведенная матрица может отображаться некорректно из-за особенности консольного вывода. Более корректно информация отображается в файле dalg.txt.

Начальную и конечную точку маршрута. После ввода данных программа осуществит вывод результатов работы: точки, через которые проходит оптимальный маршрут и длину пути (пример на рис. 8).

Рис. 8

4. После завершения задания программа предложит повторить операцию расчета (то же самое программа может предложить после некоторых ошибок ввода данных).

5.1 ПРИМЕРЫ РАБОТЫ ПРОГРАММЫ Для проверки работоспособности программы произведем расчет оптимального пути для графа, подробно рассмотренного ранее (п. 3.3), из вершины «1» в вершину «5» .

Рис. 9

Полный ход выполнения программы представлен на рисунке рисунке 10.

Рис. 10

Результаты выполнения следующие: вершины, через которые путь оптимален от первой до пятой точки 1,3,6,5 последовательно. Общая стоимость пути 20, что соответствует предыдущим расчетам.

Ниже представлено содержание текстового файла dalg. txt, с результатами работы программы:

-=== Результаты выполнения задания [test] ===;

Матрица смежности для текущего графа:

V1V1=0 V1V2=2 V1V3=4 V1V4=0

V2V1=2 V2V2=0 V2V3=1 V2V4=0

V3V1=4 V3V2=1 V3V3=0 V3V4=1

V4V1=0 V4V2=0 V4V3=1 V4V4=0

Начальная вершина: 1

Конечная вершина: 4

Расчет пути для задания [test] завершен.

Вершины, путь через которые оптимален: V1-V2-V3-V4

Длина пути: 4

-=== Результаты выполнения задания [test2] ===;

Матрица смежности для текущего графа:

V1V1=0 V1V2=7 V1V3=9 V1V4=0 V1V5=0 V1V6=14

V2V1=7 V2V2=0 V2V3=10 V2V4=14 V2V5=0 V2V6=0

V3V1=9 V3V2=10 V3V3=0 V3V4=11 V3V5=0 V3V6=2

V4V1=0 V4V2=14 V4V3=11 V4V4=0 V4V5=6 V4V6=0

V5V1=0 V5V2=0 V5V3=0 V5V4=6 V5V5=0 V5V6=9

V6V1=14 V6V2=0 V6V3=2 V6V4=0 V6V5=9 V6V6=0

Начальная вершина: 1

Конечная вершина: 5

Расчет пути для задания [test2] завершен.

Вершины, путь через которые оптимален: V1-V3-V6-V5

Длина пути: 20

Примечание: файл dalg. txt, не перезаписывается после перезапуска программы. Вместо этого он дополняется результатами обработки новых заданий.

5.2 ОБРАБОТКА ОШИБОК Большинство ошибок программы детерминированы, обработка некоторых других ошибок лежит за контекстом текущей работы. Пример обработки программой некоторых ошибок в исходных данных приведен на рисунке 11.

Рис. 11

Результаты обработки ошибок расчета алгоритма записываются в файл dalg. txt:

-=== Результаты выполнения задания [er6] ===;

Матрица смежности для текущего графа:

V1V1=0 V1V2=1 V1V3=1

V2V1=1 V2V2=0 V2V3=2

V3V1=1 V3V2=2 V3V3=0

Начальная вершина: 10

ОШИБКА выполнения. Начальная вершина задана неверно.

-=== Результаты выполнения задания [er7] ===;

Матрица смежности для текущего графа:

V1V1=0 V1V2=1

V2V1=1 V2V2=0

Начальная вершина: 1

Конечная вершина: 1

Пункт отправления равен пункту назначения. Можно никуда не идти.

ЗАКЛЮЧЕНИЕ

В процессе создания данной работы был подробно изучен алгоритм Дейкстры, а так же некоторые аспекты теории графов. Для программной реализации сего алгоритма была использована среда разработки Microsoft Visual Studio Express 2008 и входящий в него пакет Visual C++.

Задачи программирования в этой среде являются весьма распространенными, а потому практические навыки полученные в результате выполнения проекта в Microsoft Visual Studio могут быть полезны.

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

СПИСОК ИСПОЛЬУЕМЫХ РЕСУРСОВ И ЛИТЕРАТУРЫ Герберт Шилдт. Полный Справочник по «С». 4-е издание.

Пахомов Б. C/C++ MS Visual C++ 2005.

Habrahabr.ru

Citforum.ru

Firrststeps.ru

ПРИЛОЖЕНИЕ (код программы)

#include

#include

#include

using namespace std;

#define word unsigned int

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

int flag[1001];

word c[1001][1001], l[1001];

char s[8000], path[8000][1001];

char dret;

char dname[255];

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;

}

void calc ()

{

cout<<" Введите имя задания или текущую дату: «;

cin>>dname;

cout<<" Укажите количество вершин (V) графа: «;

cin>>n;

if (n>1000)

{

cout<<" Количество вершин не может быть больше 1000 (надо переопределять переменные) n" ;

cout<<" Сейчас заданы параметры: 1000, 1001, 8000″ <

getch ();

return;

}

if (n==0)

{

cout<<" Вершины не заданы. Когда вершин нет, идти неоткуда и некуда. n" ;

getch ();

return;

}

if (n==1)

{

cout<<" Выполнение с одной вершиной не имеет смысла. Мы уже на месте. n" ;

getch ();

return;

}

for (i=0;i

for (j=0;j

for (i=0;i

for (j=i+1;j

{

cout<<" Введите расстояние от V" <<<" до V" <<<": «;

cin>>c[i][j];

if (c[i][j]>2 147 483 647)

{cout<<" Расстояние не может быть больше 2 147 483 647 (надо менять тип переменных)" <

getch ();

return;

}

}

cout<<" Матрица смежности для текущего графа:" <

ofstream os («dalg.txt», ios: app); //file open. ios: app >> append to file.

cout<<" «; os << ««;

os<<" nn -=== Результаты выполнения задания [" <<" ] ===-" <

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

cout<

os<<" Матрица смежности для текущего графа:" <

for (i=0;i

{

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

for (j=0;j

{

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

os<<(«V»)<<(i+1)<<" V" <<<" ="<<(c[i][j]);

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

}

printf («nn»); os << («nn»);

}

for (i=0;i

for (j=0;j

if (c[i][j]==0) c[i][j]=2 147 483 647; //какбы бесконечность

cout<<" Укажите начальную вершину (число): «;

cin>>xn;

os<<" Начальная вершина: «<

if (xn>n)

{

cout<<" Начальная вершина задана неверно" <

os<<" ОШИБКА выполнения. Начальная вершина задана неверно." <

getch ();

return;

}

cout<<" Укажите конечную вершину (число): «;

cin>>xk;

os<<" Конечная вершина: «<

if (xk>n)

{

cout<<" Конечная вершина задана неверно" <

os<<" ОШИБКА выполнения. Конечная вершина задана неверно." <

getch ();

return;

}

xk—;

xn—;

if (xn==xk)

{

cout<<" Начальная и конечная вершины графа совпадают" <

os<<" Пункт отправления равен пункту назначения. Можно никуда не идти." <

getch ();

return;

}

for (i=0;i

{

flag[i]=0;

l[i]=2 147 483 647;

}

l[xn]=0;

flag[xn]=1;

p=xn;

itoa (xn+1,s, 1000);

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

{

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

strcat (path[i], s);

}

do

{

for (i=0;i

if ((c[p][i]≠2 147 483 647)&&(!flag[i])&&(i≠p)) //да, это оно

{

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

{

itoa (i+1,s, 1000);

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

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

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]≠2 147 483 647)

{

cout<<" Расчет пути для задания [" <<" ] завершен." <

cout<<" Вершины, путь через которые оптимален: «<<

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

os<<" Расчет пути для задания [" <<" ] завершен." <

os<<" Вершины, путь через которые оптимален: «<<

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

}

else

{

cout<<" Пути между вершинами не найдено" <

os<<" Пути между вершинами не найдено" ;

}

os.close (); //file close

}

void main ()

{

locale:global (locale («rus»));//лолшто нужно чтобы корректно букафки смотрелись в консоле

cout<<" -=== Программа реализует алгоритм Дейкстры для поиска оптимального пути ===-nn" ;

while (1)

{

calc (); //вызов функции, которая реализует основной алгоритм

cout << «nПовторить операцию? y/n «;

cin>>dret;

if (dret ≠ 'y')

{

return;

}

} //<=loop zaкрывается тут

}