МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ХАРКОВСКИЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ РАДИОЭЛЕКТРОНИКИ

Кафедра информатики

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

Тема: “Программная реализация алгоритма Дейкстры (построение цепей минимальной длины)”

по дисциплине «Программирование»

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Выполнил: Руководители:

Студент группы КИ-05-4 Руденко Д. А.

Петров О. В. Машталир С. В.

Харьков 2006

РЕФЕРАТ

Записка объяснительная к курсовой работе: 23с., 5 рис., 1 табл., 5 разделов, 3 приложения.

Объект исследования – граф с взвешенными дугами.

Цель работы – разработка демонстрационной программы использования алгоритма Дейкстры.

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

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

Программа составлена на языке С++в среде Microsoft Visual C++ 6.0. Ключевые слова: АЛГОРИТМ ДЕЙКСТРЫ, ГРАФ, ВЕРШИНА, РЕБРО, ВЕС, ПУТЬ, МАССИВ, МЕТКА,ПРОГРАММА, ТИП, ОПЕРАТОР, ФУНКЦИЯ, ЦИКЛ, МАТРИЦА СМЕЖНОСТИ.

СОДЕРЖАНИЕ

Введение………………………………………………………....……	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

ВВЕДЕНИЕ

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

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

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

Существуют три наиболее эффективных алгоритма нахождения кратчайшего пути:

· алгоритм Дейкстры (используется для нахождения оптимального маршрута между двумя вершинами);

· алгоритм Флойда (для нахождения оптимального маршрута между всеми парами вершин);

· алгоритм Йена (для нахождения k-оптимальных маршрутов между двумя вершинами).

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

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

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

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

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

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

а) объектно-ориентированное программирование (ООП);

б) унифицированный язык моделирования (UML);

в) специализированные средства разработки программного обеспечения;

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

1 ПОСТАНОВКА ЗАДАЧИ И СФЕРА ЕЁ ПРИМЕНЕНИЯ

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

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

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

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.

Если ребра не имеют ориентации, то граф называется неориентированным, (двухстороннее движение).

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

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

Так, на рис. 2.1.2 путями являются последовательности дуг:

а₆, а₅, а₉, а₈, а₄. (1)

а₁, а₆, а₅, а₉. (2)

а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

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

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

Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер ä₁, ä₂,..., ä_q, в которой каждое ребро а_i_, за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

ä₂, ä₄, ä₈, ä₁₀, (4)

ä₂, ä₇, ä₈, ä₄, ä₃, (5)

ä₁₀ , ä₇ , ä₄ , ä₈ , ä₇ , ä₂. (6)

в графе, изображенном на рис. 2.1.2, являются маршрутами; две точки над символом дуги означают, что ее ориентацией пренебрегают, т.е. дуга рассматривается как неориентированное ребро. Также путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆. Иногда дугам графа приписываются числа, называемыевесом, стоимостью, или длиной этой дуги. В этом случае граф называется графом с взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным. При рассмотрении пути µ представленного последовательностью дуг (ä₁, ä₂,..., ä_q), за его вес принимается число l(µ), равное сумме весов всех дуг, входящих в µ, т.е.

Программная реализация алгоритма Дейкстры построение цепей минимальной длины (стр. 1 из 2)

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА