Программа определения кратчайшего пути в графе

32

Оглавление:

№ страницы

Введение……………………………………………………………………....…..3

Глава 1. Теория графов…………………….…………………………….……..5

1.1. Основные понятия теории графов…………………………………..…..5

1.2. Определение кратчайшего пути в графах…………….………………...7

1.3. Метод Шимбелла…………………………………………………………8

1.4. Обзор существующих методов нахождения кратчайших путей…….10

Глава 2. Описание среды программирования……………………………...13

2.1. Pascal как язык программирования…………………………………….13

2.2. Система Pascal ABC ……………………………………………………14

Глава 3. Программа определения кратчайшего пути в графе…………...16

3.1. Реализация метода Шимбелла………………………………………….16

Заключение……………………………………………………………………...21

Библиографический список…………………………………………………..22

Приложение……………………………………………………………………..23

Введение.

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

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

Задачи поиска кратчайших и длиннейших путей на графах возникают в различных сферах жизни. Так же существуют различные алгоритмы нахождения этих самых путей. Самыми известными являются алгоритмы Дейкстры, Флоида и Шимбелла.

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

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

Главной целью курсовой работы является исследование возможностей языка программирования 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 как язык программирования.

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