Программа определения кратчайшего пути в графе
32
Оглавление:
№ страницы
Введение…………………………………………………………
Глава 1. Теория графов…………………….…………………………….…….
1.1. Основные понятия теории графов…………………………………..…..5
1.2. Определение кратчайшего пути в графах…………….………………...7
1.3. Метод Шимбелла…………………………………………………………
1.4. Обзор существующих методов нахождения кратчайших путей…….10
Глава 2. Описание среды программирования……………………………...
2.1. Pascal как язык программирования……………………………………
2.2. Система Pascal ABC ……………………………………………………14
Глава 3. Программа определения кратчайшего пути в графе…………...16
3.1. Реализация метода Шимбелла………………………………………….16
Заключение……………………………………………………
Библиографический список…………………………………………………..22
Приложение……………………………………………………
Введение.
Теория графов в качестве теоретической дисциплины может рассматриваться как раздел дискретной математики, исследующей свойства конечных множеств с заданными отношениями между их элементами.
Как прикладная дисциплина теория графов позволяет описывать и исследовать многие технические, экономические, биологические и социальные системы. Графы достаточно широко применяются в математике, технике, экономике. Знание основ теории графов необходимо в различных областях, связанных с управлением, производством, бизнесом (например, сетевой график строительства, графики доставки почты).
Задачи поиска кратчайших и длиннейших путей на графах возникают в различных сферах жизни. Так же существуют различные алгоритмы нахождения этих самых путей. Самыми известными являются алгоритмы Дейкстры, Флоида и Шимбелла.
Объектом исследования данной курсовой являются графы.
Предметом исследования является поиск кратчайших путей в графе методом Шимбелла, который позволяет находить минимальные (максимальные) пути между
вершинами, состоящие из заданного количества ребер.
Главной целью курсовой работы является исследование возможностей языка программирования Pascal для нахождения кратчайшего пути между двумя вершинами с заданным количеством ребер, а именно реализации метода Шимбелла.
Из чего следует ряд задач, поставленных на время выполнения курсовой работы:
Изучить источники информации о теории графов.
Рассмотреть возможности метода Шимбелла для нахождения кратчайшего пути в графе.
Воспользоваться возможностями Pascal как языком программирования для реализации метода Шимбелла.
Разработать программу в Pascal ABC, которая находила бы кратчайший путь методом Шимбелла.
Научиться обрабатывать фактический материал, а так же работать с ним для представления его в форме таблиц и блок-схем.
Проанализировать полученные результаты.
Глава 1. Теория графов.
Часть 1. Основные понятия теории графов.
Теория графов является разделом конечной математики, особенностью которого является геометрический подход к изучению объектов. Основное понятие теории — граф.
Графом называется совокупность конечного числа точек, называемых вершинами графа, и попарно соединяющих некоторые из этих вершин линий, называемых ребрами или дугами графа. То есть графом называется множество точек (вершин, узлов) и множество линий (ребер, дуг), которые соединяют эти точки [3].
Графы подразделяются на ориентированный (орграф) и неориентированный графы. Если в графе все элементы множества U (, (vi,vj)U) изображаются дугами, то это орграф, если ребрами – то неориентированный.
Для наглядность приведем пример ориентированного графа, когда V={v1,v2,v3,v4,v5}, U={<v1,v2>, <v2,v3>, <v4,v3>, <v4,v5>, <v5,v4>, <v5,v1>, <v5,v2>, <v3,v3>}:
Рис.1.1. Пример ориентированного графа.
И неориентированного, когда V={v1,v2,v3,v4,v5}, U={(v1,v2), (v2,v3), (v3,v4), (v4,v5), (v5,v1), (v5,v2)}:
Рис. 1.2. Пример неориентированного графа.
Примерами графов являются:
Полный граф Kn. Это граф на n вершинах, у которого смежны любые две различные вершины. Ясно, что граф Kn имеет ребер.
Граф отображения F: . Это ориентированный граф с множеством вершин Х, при этом вершины xi и хj соединяются дугой, если хj=F(хi).
Двудольные графы. Это графы, у которых множество вершин можно разбить на два множества V1, и V2,, так что каждое ребро графа соединяет только некоторую вершину из V1 с некоторой вершиной V2.
Граф единичного n-мерного куба Bn. Вершины графа- n-мерные двоичные наборы. Ребра соединяют вершины, отличающиеся одной координатой [8].
Как известно, над графами можно проделать ряд операций, которые позволяют из имеющихся графов получать другие графы с большим или меньшим количеством элементов: объединение и произведение графов, слияние и расщепление вершин [4].
Так же существуют различные способы задания графа, такие как: явное задание графа как алгебраической системы, геометрический, матрица смежности и матрица инцидентности. Матричные представления графов используются при решении прикладных задач, особенно в тех случаях, когда при моделировании предметной области применяются алгебраические доказательства [1].
Подробнее хотелось бы остановиться на матрице смежности, так как именно данный способ задания графа мы будем использовать в программе. Это квадратная матрица порядка , где n – число вершин, а - число ребер [2]. Ее строки и столбцы соответствуют вершинам графа. Если вершина i связана с вершиной j одним ребром, то элемент матрицы смежности aij = 1, если эти вершины связаны s ребрами, то аij= s. Матрица смежности вершин однозначно определяет структуру графа.
Немало важной является и матрица инциденций. Это матрица размера , где n- число вершин, а m- число ребер. Данная матрица обладает следующими свойствами: для неориентированного графа: в графе без петель каждый столбец этой матрицы имеет в точности две единицы, соответствующие паре вершин ребра; если же в графе имеются петли, то в столбцах, соответствующих петлям, имеется по одной единице, а в остальных – по две; для ориентированного: как правило, петель не содержит, его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра [1].
Часть 2. Определение кратчайшего пути.
С помощью матрицы смежности вершин можно найти все маршруты, содержащие заданное количество ребер (дуг). Каждой дуге графа можно приписать какое-либо число (вес). Такой ориентированный граф может быть представлен матрицей весов , где - вес ребра, соединяющего вершины vi и vj. Это значит, что каждой дуге поставлено в соответствие некоторое вещественное число, называемое весом данной дуги. Веса несуществующих ребер предполагаются равными 0. Матрица весов является обобщением матрицы смежности.
Для определения количества маршрутов, состоящих из n ребер (дуг), необходимо возвести в n-ю степень матрицу смежности вершин. Тогда элемент даст количество маршрутов длины, состоящих из n ребер, из начальной вершины в конечную.
Часть 3. Метод Шимбелла.
Алгоритм Шимбелла позволяет находить минимальные (максимальные) пути между вершинами, состоящие из заданного количества ребер, а так же подсчитывает длину маршрута (пути).
Введем, следуя Шимбеллу, специальные операции над элементами матрицы смежности вершин:
1. Операция умножения двух величин а и b при возведении матрицы в степень соответствует их алгебраической сумме, то есть:
2. Операция сложения двух величин а и b заменяется выбором из этих величин минимального (максимального) элемента, то есть:
Нули при этом игнорируются, а именно минимальный (максимальный) элемент выбирается из ненулевых элементов. Ноль в результате операции может быть получен лишь тогда, когда все элементы нулевые.
С помощью этих операций длины минимальных (максимальных) путей между всеми вершинами определяются возведением в степень весовой матрицы Ω (матрицы смежности – нагрузки, содержащей веса ребер). Например, элементы матрицы Ω2 вычисляются возведением в квадрат весовой матрицы:
То есть матрица составлена из целых чисел bij, которые равны числу путей длины 2, соединяющих вершины i и j. Понятно, что А3 составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины i в вершину j и т. д.
Подробнее рассмотрим нахождения кратчайшего пути методом Шимбелла на примере.
Рис.1.3. Визуальное представление графа.
Найдем кратчайшие пути из двух ребер. Для этого возведем матрицу в квадрат с учетом операций Шимбелла.
Действуя методом Шимбелла найдем первый элемент итоговой матрица:
Из полученного решения следует, что кратчайшим путем из двух ребер из a в b будет путь длиной 4. Это путь adb.
Часть 4. Обзор существующих методов нахождения кратчайших путей.
Кроме метода Шимбелла существует много различных методов нахождения кратчайших путей, некоторые из них представлены ниже:
Алгоритм Дейкстры. Содержит одно ограничение – веса ребер должны быть положительными. Сам алгоритм состоит из двух этапов. На первом находится длина кратчайшего пути, на втором – сам путь. В процессе работы алгоритма узлам графа присваиваются метки (числа) d(vi), которые служат оценкой длины (веса) кратчайшего пути от вершины s к вершине vi. Метки могут находиться в двух состояниях – быть временными или постоянными. Если метка превратилась в постоянную, это значит, что кратчайшее расстояние от вершины s до вершины vi найдено.
Этап 1. Нахождение кратчайшего пути:
Шаг 1. Присвоение вершинам начальных меток. Полагаем d(s)=0* и считаем эту мету постоянной (постоянные метки помечаются звездочками). Для остальных вершин полагаем и считаем эти метки временными. Текущую вершину обозначим , .
Шаг 2. Изменение меток. Для каждой вершины vi с временной меткой, следующей непосредственно за вершиной s, меняем метку в соответствии со следующим правилом:
Шаг 3. Превращение метки из временной в постоянную. Из вершин с временными метками выбираем вершину с наименьшим значением метки и превращаем ее в постоянную. Полагаем .
Шаг 4. Проверка на завершение 1 этапа. Если , то - длина кратчайшего пути от s до t. В противном случае происходит возврат ко второму шагу.
Этап 2. Построение кратчайшего пути:
Шаг 5. Последовательный поиск дуг кратчайшего пути. Среди вершин, непосредственно предшествующих вершине с постоянными метками находим вершину vi удовлетворяющую соотношению
Включаем дугу в искомый путь и полагаем .
Шаг 6. Проверка на завершение 2 этапа. Если , то кратчайший путь найден. Его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае происходит возврат к пятому шагу.
Алгоритм Флоида. Позволяет находить кратчайшие расстояния между всеми парами вершин в графе без циклов отрицательной длины (ребра отрицательной длины допускаются).
Алгоритм Беллмана-Мура. Если ищется кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути также должна быть минимальна [7].
Алгоритм Джонса.
Алгоритм Форда.
Шаг 0. Помечаем нулевую вершину индексом , все остальные вершины индексами .
Шаг k. Рассматриваем все дуги. Если для дуги (i, j), , то вычисляем новое значение .
Индексы устанавливаются за конечное число шагов. Обозначим - установившиеся значения индексов, которые обладают следующим свойством: величина равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину I определяется методом обратного хода [7].
Глава 2. Описание среды программирования.
Часть 1. Pascal как язык программирования.
Язык программирования является формальной знаковой системой, предназначенной для записи компьютерных программ. Он определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и те действия, которые компьютер выполнит под ее управлением.
Язык программирования предназначен для написания компьютерных программ, которые применяются для передачи компьютеру инструкций по выполнению того или иного вычислительного процесса и организации управления отдельными устройствами. Иными словами, язык программирования – это способ передачи команд, приказов, четкого руководства к действию от человека к компьютеру.
Язык программирования может использовать специальные конструкции для определения и манипулирования структурами данных и управлениями процессом вычислений [5].
Pascal является одним из языков программирования общего назначения.
Особенностями языка являются строгая типизация и наличие средств структурного (процедурного) программирования. В Pascal сведены к минимуму возможные синтаксические неоднозначности, а сам синтаксис является интуитивно понятным даже при первом знакомстве с языком.
К немало значимым достоинствам языка программирования Pascal можно отнести:
Простой синтаксис языка. Небольшое число базовых понятий. Программы на Pascal достаточно легко читаемы.
Достаточно низкие аппаратные и системные требования как самого компилятора, так и программ, написанных на Pascal.
Универсальность языка. Язык Pascal применим для решения практически всех задач программирования.
Поддержка структурного программирования, программирования "сверху-вниз", а также объектно-ориентированного программирования.
Однако, первоначально этот язык имел ряд ограничений, таких как:
Невозможность передачи функциям массивов переменной длины.
Отсутствие нормальных средств работы с динамической памятью.
Ограниченная библиотека ввода-вывода.
Отсутствие средств для подключения функций написанных на других языках.
Отсутствие средств раздельной компиляции.
Часть 2. Система Pascal ABC.
Система программирования Pascal ABC основана на языке Delphi Pascal и призвана осуществить постепенный переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию. Это система, которая содержит все основные элементы современных языков программирования: модули, классы, перегрузку операторов, интерфейсы, исключения, обобщенные классы, строку мусора, а также некоторые средства параллельного программирования [6].
Специально для учебных целей в данной системе программирования был создан ряд модулей:
Модуль растровой графики GraphABC. Он позволяет легко создавать анимацию без мерцания.
Модуль Events. Позволяет создавать простейшие событийные программы без использования объектов (события представляют собой обычные процедурные переменные).
Модули Timers и Sounds. Позволяют создавать таймеры и звуки, которые также реализованы в процедурном стиле.
Модуль контейнерных классов Containers. позволяет работать с основными структурами данных (динамические массивы, стеки, очереди, множества), реализованными в виде классов.
Модуль векторной графики ABCObjects. предназначен для быстрого изучения основ объектно-ориентированного программирования. Позволяет создавать достаточно сложные игровые и обучающие программы.
Модуль визуальных компонентов VCL. Имеется редактор форм и инспектор объектов. Технология восстановления формы по коду программы позволяет обойтись для приложения с главной формой одним файлом.
Модули исполнителей Робот и Чертёжник для быстрого обучения основам программирования школьников младших и средних классов. [5]
Глава 3. Программа определения кратчайшего пути в графе.
Часть 1. Реализация метода Шимбелла.
Программа «Определение кратчайшего пути в графе. Метод Шимбелла» разработана в среде Pascal ABC.
Программа позволяет создавать, редактировать, сохранять графы в файл, загружать из файла, визуализировать матрицы смежности. Также реализован алгоритм нахождения кратчайшего пути методом Шимбелла.
Для вычислений в программе необходимо задать количество вершин в графе, исходную и конечную вершину, количество ребер, а также задать сам граф в виде матрицы весов. Координаты точек – вершин графа, количество ребер вводит пользователь.
Интерфейс программы заключается в следующем: в правом верхнем углу расположено меню, в левом – сама матрица смежности, снизу – диалоговое окно для вывода и ввода данных.
В окне «меню» располагаются команды, которые можно проделать с графами:
Рис.3.1. Окно «Меню»
«Создать граф». При выборе этой процедуры программа предложит вам выбрать размерность символов от ‘c’ до ‘i’.
Рис.3.2. Сообщение о выборе размерности символов.
Предположим, что пользователь выбрал размерность “e”. После корректного ввода размерности создаст пустой граф.
Рис.3.3. Матрица смежности.
Граф нужно заполнить, воспользовавшись диалоговым окном.
Рис.3.4. Диалоговое окно.
«Открыть граф». Открывает граф, который введен в самой программе. «Открыть граф из документа». Просит ввести название файла, с которым Вы хотели бы работать дальше.
Рис.3.5. Сообщение о вводе названия файла для работы.
После выбора функций «Создать граф» или «Открыть граф» меню несколько изменится. Теперь перед пользователем появляется расширенное меню.
Рис.3.6. Окно расширенного «Меню».
«Изменить граф». Позволяет ввести некоторые коррективы в уже имеющийся граф.
На экран выводится матрица смежности и диалоговое окно, аналогичное тому, которое было при создании графа.
«Сохранить граф». Предназначено для сохранения графа в файл.
Рис.3.7. Сообщение о вводе названия файла для сохранения.
«Метод Шимбелла». В диалоговом окне всплывают сообщения о направлении графа, а именно из какой и в какую вершину двигаться, и за какое количество ребер. Предположим, что пользователь захотел узнать кратчайший путь из вершины “a” в “c” за 3 ребра. При этом изначально матрица смежности выглядит так:
Рис.3.8. Матрица смежности из примера.
Рис.3.9. Сообщение о вводе входных данных.
После того как все входные данные введены корректно, программа выводит на экран результат: найдет кратчайший и наидлиннейший пути между заданными вершинами.
Рис.3.10. Вывод результата на экран.
«Визуализация». Предназначено для визуального вывода графов, позволяет наглядно увидеть полученный граф. С указанием направления и подписью длины дуги.
Рис.3.11. Визуальный вывод графа.
«Выход». Завершение программы.
Сам же алгоритм нахождения кратчайшего пути между вершинами графа описан следующим модулем программы [см. приложение 3.1.1.]
Заключение.
В курсовой работе были рассмотрены основные понятия теории графов, области их применения, определение кратчайшего пути методом Шимбелла, реализованное в Pascal ABC.
В ходе работы были выполнены все поставленные ранее задачи:
Изучены источники информации о теории графов. Изучены основные понятия теории графов, операции над графами и способы его задания.
Рассмотрены возможности метода Шимбелла для нахождения кратчайшего пути в графе. Этот метод позволяет находить минимальные (максимальные) пути между вершинами, состоящие из заданного количества ребер, а так же подсчитывает длину маршрута (пути).
Воспользовалась возможностями Pascal как языком программирования для реализации метода Шимбелла.
Разработана программу в Pascal ABC, которая находила бы кратчайший путь методом Шимбелла. Программа выводит длину кратчайшего пути в графе.
Проанализированы полученные результаты.
Таким образом, можно сказать, что проведенная работа была выполнена в соответствии с поставленными в начале целями и задачами.
Библиографический список:
1. Г. Г. Асеев, О. М. Абрамов, Д. Э. Ситников. А90. «Дискретная математика». Учебное пособие. Ростов-на-Дону «Феникс», Харьков «Торсинг». 2003.
2. А. И. Белоусов, С. Б. Ткачев. «Дискретная математика»
3. О. Е. Акимов. «Дискретная математика. Логика, группы, графы». А39. Лаборатория Базовых Знаний. 2001.
4. Берж К. «Теория графов и ее применения». Издательство иностранной литературы. Москва. 1962.
5. Википедия. Свободная энциклопедия. http://ru.wikipedia.org/wiki/
6. Интернет ресурс. http://sunschool.math.rsu.ru/
7. В. Н. Бурков, Д. А. Новиков. «Элементы теории графов»
8. В. А. Носов. «Комбинаторика и теория графов». 1999.
Приложения.
1.1.1. Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых
2.3.1. Паскаль был создан Никлаусом Виртом в 1968-69 годах. Он был опубликован в 1970 году Виртом как небольшой и эффективный язык, чтобы способствовать хорошему стилю программирования, использовать структурное программирование и структурированные данные.
Название языку дано в честь выдающегося французского математика, физика, литератора и философа Блеза Паскаля, так как он создал первую в мире механическую машину, складывающую 2 числа.
3.1.1. procedure Shimbella;
var s,z,i,k:char;
mas:arr;
min:integer; {для минимального пути}
max:integer; {для максимельного пути}
matr2:array['a'..'i', 'a'..'i'] of integer;
leave,dest:char; {куда, откуда}
kolvo,c:integer; {кол-во ребер}
function min_mas(mas:arr):integer; {наикратчайший путь}
begin
min:=mas['a'];
for s:='a' to n do
if (mas[s]<>0) then
if min=0 then min:=mas[s]
else if mas[s]<min then min:=mas[s];
min_mas:=min; {нашли мин.}
end;
function max_mas(mas:arr):integer;
begin {аналогичным образом, но}
max:=mas['a'];
for s:='a' to n do
if (mas[s]<>0) then
if max=0 then max:=mas[s]
else if mas[s]>max then max:=mas[s];
max_mas:=max;
end;
function mnozh(matr,matr2:arr2):arr2; {для минимального пути}
var i,k,z:char;
matr3:arr2;
begin
for i:='a' to n do
for k:='a' to n do begin
for z:='a' to n do begin
mas[z]:=matr[i,z]+matr2[z,k];
if mas[z]=matr[i,z] then mas[z]:=0; {(хотя бы одно из них = 0)}
if mas[z]=matr2[z,k] then mas[z]:=0; {то значение тоже = 0}
end;
matr3[i,k]:=min_mas(mas);
end;
mnozh:=matr3;
end;
function mnozh2(matr,matr2:arr2):arr2;
var i,k,z:char;
matr3:arr2;
begin
for i:='a' to n do
for k:='a' to n do begin
for z:='a' to n do begin
mas[z]:=matr[i,z]+matr2[z,k];
if mas[z]=matr[i,z] then mas[z]:=0; {(хотя бы одно из них = 0)}
if mas[z]=matr2[z,k] then mas[z]:=0; {то значение тоже = 0}
