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

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

Департамент образования города Нижний Новгород

Государственное образовательное учреждение

высшего профессионального образования

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. Р.Е. Алексеева

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

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

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

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

г. Нижний Новгород - 2010 г

СОДЕРЖАНИЕ

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

. Введение

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

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

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

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

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

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

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

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

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

.2 Обработка ошибок

Заключение

Список используемых ресурсов и литературы

Приложение (код программы)

ПОСТАНОВКА ЗАДАЧИ

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

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

ВВЕДЕНИЕ

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

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

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

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

3.1 ОБЩИЕ СВЕДЕНЬЯ О ГРАФАХ

Для реализации алгоритма необходимо использовать граф. В математической теории графов <#"784319.files/image001.gif"> <#"784319.files/image002.gif"> <#"784319.files/image003.gif">

Рис. 2

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

Рис. 3

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й (рис. 3). На этом этапе все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра <#"784319.files/image005.gif">

Рис. 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

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

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

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

Кроме стандартных функций из библиотек были использованы также следующие функции:minim(word x, word y) - функция, которая возвращает минимальное из x и y.

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

схема 4

4.2 СРЕДА РАЗРАБОТКИ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ

В качестве среды для разработки программного обеспечения была выбрана Microsoft Visual Studio Express 2008, средства Visual C++. Microsoft Visual Studio Express - линейка бесплатных <#"784319.files/image018.gif">

Рис. 8

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

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, не перезаписывается после перезапуска программы. Вместо этого он дополняется результатами обработки новых заданий.

Большинство ошибок программы детерминированы, обработка некоторых других ошибок лежит за контекстом текущей работы. Пример обработки программой некоторых ошибок в исходных данных приведен на рисунке 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..ru.ru.ru

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

#include <iostream>

#include <conio.h>

#include <fstream>namespace std;

#define word unsigned inti, j, n, p, xn, xk;flag[1001];c[1001][1001], l[1001];s[8000], path[8000][1001];dret;dname[255];min(int n)

{i, result;(i=0;i<n;i++)(!(flag[i])) result=i;(i=0;i<n;i++)((l[result]>l[i])&&(!flag[i])) result=i;//окresult;

}minim(word x, word y)

{(x<y) return x;y;

}calc()

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

cin>>dname; <<"Укажите количество вершин (V) графа: ";>>n; (n>1000)

{<<"Количество вершин не может быть больше 1000 (надо переопределять переменные)\n";<<"Сейчас заданы параметры: 1000, 1001, 8000"<<endl;();;

}(n==0)

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

}(n==1)

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

getch();;

}(i=0;i<n;i++)//Гы Гы Гы(j=0;j<n;j++) c[i][j]=0;(i=0;i<n;i++)(j=i+1;j<n;j++)

{

cout<<"Введите расстояние от V"<<i+1<<" до V"<<j+1<<": ";

cin>>c[i][j];(c[i][j]>2147483647)

{cout<<"Расстояние не может быть больше 2147483647 (надо менять тип переменных)"<<endl;();;

}

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

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

cout<<" "; os << " ";<<"\n\n -=== Результаты выполнения задания ["<<dname<<"] ===-"<<endl<<endl;

for(i=0;i<n;i++) { cout<<" V"<<i+1;}

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

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

{("V%d",i+1);(j=0;j<n;j++)

{("%6d",c[i][j]); <<(" V")<<(i+1)<<"V"<<j+1<<"="<<(c[i][j]);[j][i]=c[i][j];

}("\n\n"); os << ("\n\n");

}(i=0;i<n;i++)(j=0;j<n;j++)

if(c[i][j]==0) c[i][j]=2147483647; //какбы бесконечность<<"Укажите начальную вершину (число): ";>>xn;<<"Начальная вершина: "<<xn<<endl;(xn>n)

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

}<<"Укажите конечную вершину (число): ";>>xk;<<"Конечная вершина: "<<xk<<endl<<endl;(xk>n)

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

getch();;

}-;-;(xn==xk)

{<<"Начальная и конечная вершины графа совпадают"<<endl;<<"Пункт отправления равен пункту назначения. Можно никуда не идти."<<endl;

getch();;

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

{[i]=0;[i]=2147483647;

}[xn]=0;[xn]=1;=xn;(xn+1,s,1000);(i=1;i<=n;i++)

{(path[i],"V");(path[i],s);

{(i=0;i<n;i++)//тут((c[p][i]!=2147483647)&&(!flag[i])&&(i!=p)) //да, это оно

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

{(i+1,s,1000);(path[i+1],path[p+1]);(path[i+1],"-V");(path[i+1],s);

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

} //не помню что это за хрень выше, но без нее не работает.

p=min(n);[p]=1;

}(p!=xk);(l[p]!=2147483647)

{<<"Расчет пути для задания ["<<dname<<"] завершен."<<endl;<<"Вершины, путь через которые оптимален: "<<path[p+1]<<endl;<<"Длина пути: "<<l[p]<<endl;<<"Расчет пути для задания ["<<dname<<"] завершен."<<endl;<<"Вершины, путь через которые оптимален: "<<path[p+1]<<endl;<<"Длина пути: "<<l[p]<<endl;

}

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

}.close(); //file close

}main()

{::global(locale("rus"));//лолшто нужно чтобы корректно букафки смотрелись в консоле<<"-=== Программа реализует алгоритм Дейкстры для поиска оптимального пути ===-\n\n";(1)

{(); //вызов функции, которая реализует основной алгоритм<< "\nПовторить операцию? y/n ";

cin>>dret;(dret != 'y')

{;

}

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

}