Содержание

Введение 5

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

2. Теоретический раздел 10

2.1 Сведения о графах 14

2.2 Описание алгоритма 15

2.3 Полиномиальная сводимость, NP – полная задача 20

3. Проектный раздел 18

3.1 Описание алгоритма и структуры программы 18

3.2 Формальная постановка 20

3.3 Описание программных средств 21

4. Экспериментальный раздел 24

Заключение 32

Список использованных источников 33

Приложение А – листинг программы 34

Приложение Б – результат 50

Введение

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

Графы используются в строительстве при планировании проведения работ; для решения логических проблем, связанных с перебором вариантов и во многих других вопросах.

Впервые основы теории графов появились в работе Л.Эйлера, где он описывал решения головоломок и математических развлекательных задач. Широкое же развитие теория графов получила лишь в 50-х годах ХХ века в связи со становлением кибернетики и развитием вычислительной техники.

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

Целью курсовой работы является закрепление знаний по дисциплине «Структуры и алгоритмы обработки данных», практическое овладение математическим аппаратом, характерным для современной теории анализа сложных систем (теории графов) .

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

Нахождение кратчайшего пути – жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (например, кратчайший путь от дома до университета), в системах автопилота, для нахождения оптимального маршрута при перевозках, коммутации информационного пакета в Internet и т.п.

Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом.

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

Количество объектов усложнялись, увеличивались, и натурное моделирование (макеты сооружений) стало невыгодным, неэкономным. Поэтому для изучения начали применять математику. Использование математических моделей – уравнения, неравенства, формулы и тому подобное называется математическим моделированием, для развития и приспособления которого нужны были эффективные численные методы.

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

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

Из всех объектно-ориентированных языков С++ является наиболее широко используемым. И именно с его помощью в данном курсовом проекте реализуется алгоритм Дейкстра.

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

Основной задачей данного курсового проекта является программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа.

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

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

2. Теоретический раздел

1. Сведения о графах

В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.

Граф G задается множеством точек (вершин) х₁, х₂,..., х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А). Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Геометрический граф в пространстве jⁿ (Эвклидово пространство) – это множество V={v_i} точек пространства jⁿ и множество Е={e_k} простых кривых удовлетворяющих следующим условиям:

1) Каждая замкнутая прямая из множества Е содержит только одну точку v множества V;

2) Каждая незамкнутая прямая из множества Е содержит только 2 точки v из множества V, которые являются ее границами.

3) Кривые Е не имеют общих точек за исключением точек из множества V

4) Граф – это совокупность не пустого множества V, изолированного от него множества Е и отображения f: ЕVV.

5. Если граф не имеет ребер, он называется вырожденным. Если множества Е и V конечные, то граф называется конечным.

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

Алгори́тм Де́йкстра (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э.Дейкстрой в 1959г. Алгоритм Дейкстра строит кратчайшие пути, ведущие из исходной вершины графа к остальным вершинам этого графа (если таковые имеются). Алгоритм работает только для графов без ребер отрицательного веса.

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

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

Словесное описание алгоритма

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

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

Рисунок 1 – Блок-схема алгоритма Дейкстра