Теоретическое исследование вопроса и практическое применение. Общие сведения о графах. Алгоритм Дейкстры. Особенности работы в среде. Программная реализация. Описание алгоритма и структуры программы. Описание программных средств. Текст программы.
Аннотация к работе
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п. Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути: · алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами); При увеличении их количества задача поиска кратчайшего пути усложняется. Благодаря появлению компьютеров и развитию информационных технологий создаются методы и средства компьютерного моделирования, способные решать сложные практические задачи, такие как управление большими энергетическими системами, создание достоверных прогнозов погоды или урожая, моделирование региональных и общегосударственных систем, проектирование самолетов, кораблей и т. п.Программа должна работать так, чтобы пользователь вводил количество вершин и длины ребер графа, а после обработки этих данных на экран выводился кратчайший путь между двумя заданными вершинами и его длина.Граф G (рис.2.1.1) задается множеством точек (вершин) х1, х2,..., xn. Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом. Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение). В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин, ее направление предполагается заданным от первой вершины ко второй. Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.Алгоритм Дейкстры строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются). Причем вершина, помеченная последней (на данный момент) расположена ближе к исходной вершине, чем все непомеченные, но дальше, чем все помеченные. Сначала помечается исходная вершина; следующей, очевидно, будет помечена вершина, ближайшая к исходной, и смежная с ней. Известны кратчайшие пути, ведущие из исходной вершины к помеченным.При написании программы использовалась среда Microsoft Visual C 6.0. В ходе написания программы все операторы и служебные слова языка С выделяются другим цветом, чтобы отличать их от переменных, заданных программистом. Вверху находится стандартная панель - Standart, с которой можно сохранить исходный текст программы на диск, открыть новый документ, скопировать или вставить текст, отменить последнее действие, или найти текст.Программа выводит минимальный путь между двумя указанными вершинами в графе и его длину. При запуске программы на экран выводится запрос о вводе весов ребер исследуемого графа. Следующим этапом выполнения программы является запрос о вводе номеров вершин, между которыми необходимо узнать путь. В случае, если начальная и конечная вершины совпадают, отображается соответствующее сообщение и работа программы завершается. Переменная Тип Описание n int Количество точек (вершин) грифа i,j int Счетчики p int Номер кратчайшего пути и наименьшей длины пути xn int Номер начальной точки (вершины) xk int Номер конечной точки (вершины) flag[11] int Массив, i-й элемент которого имеет значение 0, когда i-й путь и расстояние временные, и принимает значение 1, когда i-й путь и расстояние становятся постоянными c[11][11] word (unsigned int) Массив i-j элемент которого содержит расстояние между i-й и j-й точками (вершинами) Замечание: 1. с[i][i]=? 2. c[i][j]=c[j][i] s[80] char Строчная переменная, которая содержит промежуточные значения пути path[80][11] char Массив строк, который содержит пути Замечание: После прохождения обработки по алгоритму Дейкстры р-й элемент массива содержит кратчайший путь. l[11] word (unsigned int) Массив, который содержит длины путей (path) Замечание: После прохождения обработки по алгоритму Дейкстры р-й элемент массива содержит длину кратчайшего пути.При запуске программы на экране появится окно с инструкциями. Введите количество вершин исследуемого графа. Введите веса ребер (положительное число).Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual C 6.0. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование».5. Конспект лекций.
План
СОДЕРЖАНИЕ
Введение………………………………………………………....…… 4
1 Постановка задачи и сфера ее применения…..………………...... 6
2 Теоретическая часть…………………………………….………..... 7
2.1 Общие сведения о графах……………………………...……. 7
2.2 Алгоритм Дейкстры….……………………………………... 9
3 Особенности работы в среде ……………………….……………. 10
4 Программная реализация………………………………….……. 11
4.1 Описание алгоритма и структуры программы…………….. 11
4.2 Описание программных средств……………………………. 13
5 Инструкция пользователя…………………………………………. 15
Заключение….…………………………………………………….…. 16
Перечень ссылок……………………………………………………... 17
Приложение А Текст программы………………………………….. 18
Приложение Б Результат………..……………………………….….. 22
Приложение В Схема программной реализации алгоритма Дейкстры….. 23
Вывод
Таким образом, в процессе создания данного проекта разработана программа, реализующая алгоритм Дейкстры в Microsoft Visual C 6.0. Ее недостатком является примитивный пользовательский интерфейс. Это связано с тем, что программа работает в консольном режиме, не добавляющем к сложности языка сложность программного оконного интерфейса
Также были углублены знания, полученные в процессе выполнения лабораторных работ по предмету «Программирование».
ПЕРЕЧЕНЬ ССЫЛОК
1. Бондарев В.М. Программирование на С .-Х: «Компания СМИТ», 2004
2. Страуструп Бьярн Язык программирования С (2 ч).-«К:ДИАСОФТ», 1993
3. Хаханов В.И., Чумаченко С.В. Дискретная математика (теоретическое и практическое содержание курса).-Кафедра АПВТ, 2002