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

Задачей данного курсового проекта является разработка программного обеспечения для реализации алгоритма, позволяющего находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса (алгоритма Дейкстры). Этот алгоритм позволяет находить кратчайшее расстояние от одной из вершин графа до всех остальных, при условии, что ребра графа не имеют отрицательного веса.Для реализации алгоритма необходимо использовать граф.Алгоритм Дейкстры ищет кратчайшие маршруты, идущие из первой вершины графа к остальным вершинам этого графа. Во время работы алгоритма последовательно помечаются рассмотренные вершины графа. Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные. Сначала помечается первая вершина.Пусть требуется найти расстояния от 1-й вершины до всех остальных. Кружками обозначены вершины, линиями - пути между ними (ребра графа). Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1. Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й (рис. Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещенные.Для обозначения были использованы следующие переменные: Переменная Тип Описание n int Количество точек (вершин) графа i,j int Счетчики p int Номер кратчайшего пути и наименьшей длины пути xn int Номер начальной точки (вершины) xk int Номер конечной точки (вершины) flag[1001] int Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постоянными c[1001][1001] word (unsigned int) Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: с[i][i]=? c[i][j]=c[j][i] s[8000] char Строчная переменная, которая содержит промежуточные значения пути path[8000][1001] char Массив строк, который содержит пути Замечание: После прохождения обработки по алгоритму Дейкстры р-й элемент массива содержит кратчайший путь. l[1001] word (unsigned int) Массив, который содержит длины путей (path) Замечание: После прохождения обработки по алгоритму Дейкстры р-й элемент массива содержит длину кратчайшего пути.На схеме 1 изображена блок-схема работы программы. Блок обрабатывающий алгоритм Дейкстры называется "Алгоритм Дейкстры" (к.о.) Его подробный алгоритм представлен ниже, на схеме 2. При запуске программы на экран выводится запрос о вводе весов ребер исследуемого графа. Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь.Microsoft Visual Studio Express - линейка бесплатных интегрированных сред разработки , облегченная версия Microsoft Visual Studio , разработанной компанией Microsoft .Программа имеет консольный текстовый интерфейс. После запуска программы появится окно с инструкциями ввода информации для определения графа (отображение реализовано через матрицу смежности). После выполнения программа создает текстовый файл dalg.txt, в который добавляет результат выполнения после каждого задания (включая неудачные). Для вычисления пути согласно алгоритму необходимо ввести: Имя задания (либо текущую дату). Программа последовательно запросит пользователя ввести расстояния между вершинами.Для проверки работоспособности программы произведем расчет оптимального пути для графа, подробно рассмотренного ранее (п.3.3), из вершины "1" в вершину "5". Полный ход выполнения программы представлен на рисунке рисунке 10. Результаты выполнения следующие: вершины, через которые путь оптимален от первой до пятой точки 1,3,6,5 последовательно. Ниже представлено содержание текстового файла dalg.txt, с результатами работы программы:-=== Результаты выполнения задания [test] ===- Расчет пути для задания [test] завершен.Большинство ошибок программы детерминированы, обработка некоторых других ошибок лежит за контекстом текущей работы. Пример обработки программой некоторых ошибок в исходных данных приведен на рисунке 11. Результаты обработки ошибок расчета алгоритма записываются в файл dalg.txt:-=== Результаты выполнения задания [er6] ===- Начальная вершина задана неверно.В процессе создания данной работы был подробно изучен алгоритм Дейкстры, а так же некоторые аспекты теории графов. Для программной реализации сего алгоритма была использована среда разработки Microsoft Visual Studio Express 2008 и входящий в него пакет Visual C . Задачи программирования в этой среде являются весьма распространенными, а потому практические навыки полученные в результате выполнения проекта в Microsoft Visual Studio могут быть полезны.cout<<"Укажите количество вершин (V) графа: "; Когда вершин нет, идти неоткуда и некуда.

"; {cout<<"Выполнение с одной вершиной не имеет смысла. {cout<<"Начальная вершина задана неверно"<<endl; Начальная ве

СОДЕРЖАНИЕ

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

2. Введение

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

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

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

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

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

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

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

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

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

5.2 Обработка ошибок

Заключение

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

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

ПОСТАНОВКА ЗАДАЧИ алгоритм дейкстра программный граф

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

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

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

СПИСОК ИСПОЛЬУЕМЫХ РЕСУРСОВ И ЛИТЕРАТУРЫ

Герберт Шилдт. Полный Справочник по "С". 4-е издание.

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

Habrahabr.ru

Citforum.ru

Firrststeps.ru