Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(национальный исследовательский университет)»

Филиал «Восход»

Отчёт

по курсовой работе

Математическая логика и теория графов

Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла

Жукова М.А.

Байконур 2023 г.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего профессионального образования

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

КАФЕДРА Б22-М И ПОИС

ИНДИВИДУАЛЬНОЕ ЗАДАНИЕ

на курсовую работу

Студенту специальности	01.03.04	«Прикладная математика»,	курса	1
группы	ДМ1-47
Фамилия, имя, отчество	Жукова Маргарита Андреевна
Тема: «Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла»
Целевая установка (конечный результат работы)	Сформировать представление
о методе и алгоритме нахождения кратчайших путей от каждой вершины -
источника к каждой вершине ориентированного графа
Исходные данные	Выполнение задание согласно варианту 5
Начало проектирования		Окончание проектирования
Задачи, решаемые в ходе работы (последовательность выполнения работы):
1. Анализ современного состояния вопроса
2. Построение математической модели
3. Разработка алгоритма решения задачи
4. Получение результатов и их интерпретация
5. Анализ результатов
Отчётный материал: пояснительная записка на 35 листах; презентация Power Point на _____ слайдах
Место выполнения работы (организация, подразделение)
филиал «Восход» МАИ (ГТУ) кафедра Б22 - МиПОИС, г. Байконур

Аннотация

Данная курсовая работа - «Поиск кратчайшего пути. Алгоритм Флойда-Уоршолла» подготовлена студенткой 1-го курса «Московского авиационного института (национальный исследовательский университет) филиал «Восход» по направлению (специальности) подготовки 01.03.04 - «Прикладная математика», группы ДМ1-47 Жуковой М.А. под руководством преподавателя дисциплины «Математическая логика и теория графов» Тарасенко А.А.

Работа состоит из двух разделов. В первом разделе «Теоретическая часть» рассмотрены основные понятия теории графов - одного из разделов современной математики, рассмотрено применение алгоритмов в поиске кратчайших путей в графах, дано правила представление логической структуры алгоритма Флойда -Уоршелла как средства поиска кратчайших путей между всеми парами вершин во взвешенных графах., приводятся инструментальные средства решения оптимизационных задач на графах - Maple, Matlab.

Во втором разделе «Алгоритмическая часть» описывается решение поставленных задач и производится анализ полученных результатов согласно заданию на курсовую работу.

Работа включает 35 страниц, выполнена с использованием 12 источников, содержит 9 таблиц, 14 фотографических изображений (рисунков).

1.Теоретическая часть

Введение

Графы как структуры данных широко применяются при решении многих задач. Они могут использоваться для представления данных, моделей процессов, структур программ и так далее. Многие задачи, решаемые с использованием графов, относятся к задачам выбора. Поиск в графах играет важную роль при анализе больших наборов данных. Широкое применение в задачах маршрутизации и логистики имеют алгоритмы поиска кратчайших путей. Одним из наиболее используемых на практике алгоритмов для поиска кратчайших путей между всеми парами вершин во взвешенных графах является алгоритм Флойда - Уоршелла. Он служит основой для получения эффективных параллельных версий алгоритма для реализации на многоядерных центральных процессорах, компьютерах с распределенной памятью, графических процессорах (GPU).

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

В данной работе построенный обобщенный алгоритм Флойда - Уоршелла реализован на графическом процессоре, при вычислениях на котором быстрым является процесс обращения к регистрам, разделяемой памяти мультипроцессора и кешам, но не обращение к глобальной памяти GPU. Реализация на основе обобщенного алгоритма приводит к сокращению числа обращений к глобальной памяти и, как показали вычислительные эксперименты, к уменьшению времени выполнения.

1.1 Основные определения теории графов

Граф G = (V,E) включает непустое множество V, называемое множеством вершин (узлов) графа, множество Е, представляющее собой множество ребер графа и отображение множества ребер на множество пар элементов из множества V. Множества V и Е конечны. Из определения следует, что каждому ребру графа x можно поставить в соответствие пару вершин этого графа, тогда говорят, что ребро соединяет вершины u и v. Любые две вершины u и v, соединенные в графе ребром x называются смежными, и говорят, что ребро х инцидентно вершинам u и v. Граф, у которого каждая вершина смежна со всеми остальными вершинами, называется полным графом.

Ребро x, направленное от одной вершины u к другой v, называется ориентированным ребром, или дугой. Граф, содержащий только ориентированные ребра, называется ориентированным графом (орграфом). Ребро, не имеющее определенного направления, называется неориентированным ребром. Граф содержащий неориентированные рёбра называется неориентированным. Граф, содержащий как ребра, так и дуги, называется смешанным графом.

Графическому представлению ориентированного графа с 6 вершинами и 8 дугами, приведенному на Рисунке 1, соответствует граф G = (V,E), у которого

V = {1,2,3,4,5,6} и Е ={(1,2),(1,3),(3,2),(3,4),(3,5),(4,5),(5,6),(6,4)}.

Рисунок 1 - Ориентированный граф

Ребро х, соответствующее упорядоченной паре вершин (u,v), начинается в вершине u (исходит из u) и заканчивается в вершине v (входит в v), u -- начальная вершина ребра (дуги), v -- конечная. Ребро, соединяющее некоторую вершину саму с собой, называется петлей, в нашем рассмотрении петли не допускаются. В случае ориентированных ребер между парой вершин возможны два ребра, которые имеют противоположную направленность и считаются разными ребрами х₁= (u,v), х₂= (v,u). Если между любой парой вершин графа имеется не более одного ребра в неориентированном графе или не более одного ребра данного направления в ориентированном графе, то такой граф называется простым, в противном случае -- мультиграфом.

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

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

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

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

1.2 Представление графов

Реализация алгоритмов обработки графов в виде машинных процедур в высокой степени зависит от способа представления графов на логическом и физическом уровнях. А способ представления графа существенно зависит от типов структур данных, допускаемых используемым языком программирования и типом ЭВМ. Выбор наилучшего способа представления графа зависит от природы моделируемых данных (процессов) и операций, выполняемых над ними. На выбор подходящего представления влияют такие факторы, как число вершин, максимальная полустепень исхода, частота изменения числа вершин и ребер, является ли граф ориентированным или нет и т.д. Таким образом, какого-то одного наилучшего способа представления не существует, лучшее представление зависит от решаемой задачи. Выбор конкретного представления графа может существенно повлиять на эффективность его обработки.

Граф G=(V,E) может быть полностью определён простым перечислением двух множеств V и E. Однако в большинстве случаев этот способ представления не позволяет создавать эффективные алгоритмы обработки графов.

Широко распространенным способом представления графов являются матричный способ и соответствующее отображение их в векторной (смежной) памяти в виде двухмерных массивов. Этот способ имеет несомненные достоинства:

а) массивы легко хранить и обрабатывать в ЭВМ;

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

в) имеются хорошо известные алгоритмы обработки графов.

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

1.2.1 Матрица смежности

Очень часто граф представляется в виде матрицы смежности А_n*n, в которой а_ij=1, если (v_i,v_j) принадлежит Е, а_ij=0 в противном случае.

Для простых неориентированных графов матрица смежности симметрична, т.е. A_ij=a_ji. В случае взвешенного графа полагается a_ij=w_ij, где w_ij -- вес ребра.

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

Используя матрицу смежности, можно определить все пути между вершинами v_i и v_j и их длины, определить все возможные пути, циклы, простые и элементарные пути.

Рассмотрим представление орграфа G₁ и неориентированного графа G₂ в виде матриц смежности (Рисунок 2).



Рисунок 2 - Ориентированный (G₁) и неориентированный (G₂)графы

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

При разработке программ, предназначенных для работы с графами, необходимо контролировать правильность задания параметров графа. При числе вершин графа, меньших 2, не приходится говорить о матрице смежности. Если m -- число вершин графа и n -- число дуг, очевидными являются требования: m?2, n?1 и n?m*(m - 1) для ориентированного или n?m*(m - 1)/2 для неориентированного графа. Здесь учитывается тот факт, что в ориентированном графе вершины могут быть соединены прямыми и обратными дугами.

1.2.2 Векторы смежности

При представлении графа в виде векторов смежности создается матрица, число строк которой равно числу вершин графа. Каждая i-я строка матрицы содержит номера вершин, смежных с i-той вершиной, петли исключаются. Число столбцов матрицы определяется максимальной полустепенью исхода в орграфе или максимальной степенью в неориентированном графе.

Представление векторов смежности массивами:

G1 G2

2 3 0 2 4 0 0 0

0 0 0 1 3 4 0 0

2 4 5 2 4 0 0 0

5 0 0 1 2 3 5 6

6 0 0 4 6 0 0 0

4 0 0 4 5 0 0 0

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

1.2.3 Списки смежности

Список смежности для вершины v -- это для орграфа список концов дуг, исходящих из вершины v, а для неориентированно графа -- список смежных с v вершин. Для орграфа G₁ и графа G₂ списки смежности выглядят так:

G₁ G₂

1 => 2>3 1=> 2>4

2=> NULL 2=> 1>3>4

3=> 2>4>5 3=> 2->4

4=>5 4=>1>2>3>5>6

5=>6 5=>4>6

6 =>4 6=>4>5

Здесь: => -- указатель начала списка, > связь вершин в списке смежности.

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

1.2.4 Матрица инцидентности

Любые две вершины u и v, соединенные в графе ребром а, называются смежными, и говорят, что ребро а инцидентно вершинам u и v.

Любой граф можно задать матрицей инцидентности. Матрица инцидентности B[b_ij] размерностью n*m (n -- число шин, m -- число дуг) определяется следующим образом: b_ij=+1 если u_i является начальной вершиной дуги a_j; b_ij=-l, если u_i является конечной вершиной дуги а_j; b_ij=0 в противном случае.

Если граф неориентированный, то его матрица инцидентности определяется аналогично, за исключением того, что элемент -1 поменяется на +1.

1.3 Пути в графе

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

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

Так на рисунке 3 последовательности дуг

а₆, а₅, а₉, а₈, а₄

а₁, а₆, а₅, а₉,

а₁, а₆, а₅, а₉, а₁₀, а₆, а₄

являются путями.

Дуги а=(x_i, x_j), x_i?x_j, имеющие общие концевые вершины, называются смежными. Две вершины x_i и x_j называются смежными, если какая-нибудь из двух дуг (x_i, x_j) и (x_j, x_i) или обе одновременно присутствуют в графе.

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

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

Рисунок 3 - Последовательности дуг и вершин в ориентированном графе.

Маршрут есть неориентированный «двойник» пути. Понятие рассматривается в том случае, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер , в которой каждое ребро , за исключением первого и последнего ребер, связано с ребрами и своими двумя концевыми вершинами.

Путь или маршрут можно изображать также последовательностью вершин х₅, х₅, х₄, х₈, х_3, х_{5, ,} х₆ .

1.4 Вес и длина пути

Иногда дугам графа G сопоставляются (приписываются) числа - (x_i, x_j) ставится в соответствие некоторое число c_ij, называемое весом или длиной, или стоимостью (ценой) дуги. Тогда граф G называется графом с взвешенными дугами. Иногда веса приписываются вершинам x_i графа, и тогда получается граф с взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.

При рассмотрении пути м, представленного последовательностью дуг (a₁, a₂, …, a_q), за его вес (или длину, или стоимость) принимается число l(м), равное сумме весов всех дуг, входящих в м, то есть

(1.4)

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

Длиной (или мощностью) пути м называют число дуг, входящих в него.

1.5 Петли, ориентированные циклы и циклы

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

Рисунок 4 - Петли в ориентированном графе.

Путь a₁, a₂, …, a_q называется замкнутым, если в нем начальная вершина дуги а₁ совпадает с конечной вершиной дуги а_q.

Замкнутый маршрут является неориентированным двойником замкнутого пути. Таким образом, замкнутый маршрут является маршрутом x₁, x₂, …, x_q, в котором совпадают начальная и конечная вершины, то есть x₁=x_q.

1.6 Степени вершины

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

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

где n - число вершин и m - число дуг графа G.

1.7 Алгоритмы обхода графа

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

Наиболее известными из таких алгоритмов являются поиск в глубину (depth first search, DFS) и поиск в ширину (breadth-first search, BFS).

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

- неоткрытая - первоначальное состояние вершины;

- открытая - вершина обнаружена, но инцидентные ей ребра не просмотрены;

- обработанная (помеченная) - все ребра, инцидентные этой вершине, посещены.

1.7.1 Поиск в ширину

Пусть задан граф G = (V, E) и выделена начальная вершина v. Алгоритм поиска в ширину систематически обходит все ребра графа G для «открытия» всех вершин, достижимых из v. В процессе обхода строится дерево поиска в ширину с корнем в начальной вершине, содержащее все достижимые вершины.

Поиск в ширину имеет такое название, так как в процессе обхода графа помечаются все вершины на расстоянии k, прежде чем начнется обработка любой вершины на расстоянии k+1. Алгоритм работает как для ориентированных, так и для неориентированных графов. Идея алгоритма: все вершины, смежные с начальной, открываются, то есть помещаются в список, и получают единичную пометку. После этого начальная вершина обработана полностью и имеет пометку 2. Следующей текущей вершиной становится первая вершина списка. Все ранее не помеченные вершины, смежные с текущей, заносятся в конец списка (становятся открытыми). Текущая вершина удаляется из списка и помечается числом 2. Процесс продолжается, пока список вершин не пуст. Такая организация списка данных называется очередью.

Рисунок 5 - Просмотр вершин графа в процессе поиска в ширину

При реализации поиска в ширину используется массив пометок Mark, массив предков Parent и очередь Q. Первоначально каждой вершине в массиве Mark соответствует значение 0, то есть вершина неоткрытая. Вершина открывается при первом посещении, и ее пометка изменяется на 1. Когда все ребра, исходящие из вершины, исследованы, то она считается обработанной и имеет пометку 2. При просмотре списка вершин, смежных с текущей, открываются новые вершины. При этом их предком считается текущая вершина. Эта информация сохраняется в массиве Parent и позволяет восстановить дерево поиска в ширину. Для графа, изображенного на рисунке 5, массив предков будет иметь вид (Таблица 1):

Таблица 1 - Матрица смежности

Вершина	0	1	2	3	4	5	6	7
Предок	0	0	0	0	1	2	4	6

1.7.2 Поиск в глубину

Основная идея поиска в глубину, как и следует из его названия, состоит в том, чтобы идти «вглубь» графа, пока это возможно. Просмотр начинается с некоторой начальной вершины v. Она считается «открытой». Выбирается вершина u, смежная с v, открывается, то есть помечается значением 1, и процесс повторяется с одной из вершин, смежных с u.

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

В процессе обхода графа строится дерево поиска в глубину. Вершина v, через которую открывается вершина u, является ее предком. Эта информация сохраняется в массиве Parent.

Для определения состояния вершины (неоткрытая, открытая или обработанная), как и раньше, используется массив пометок Mark. Если вершина i открыта, то Mark[i] = 1, обработана - 2, в исходном состоянии Mark[i] = 0. Для хранения последовательности открытых, но необработанных вершин используется стек. Эта структура данных обеспечивает возврат к предыдущей открытой вершине.

Также с каждой вершиной связываются две метки времени: время открытия вершины time_in и время завершения ее обработки time_out.

Порядок просмотра вершин графа при поиске в глубину представлен на рисунке 6.

Рисунок 6 - Порядок просмотра вершин графа при поиске в глубину

1.8 Кратчайшие пути

Пусть дан граф G = (V, E), ребрам (или дугам в случае ориентированного графа) которого приписаны веса (стоимости), задаваемые взвешенной матрицей смежности A. Задача о кратчайшем пути состоит в нахождении кратчайшего пути от заданной начальной вершины до заданной конечной вершины t, при условии, что такой путь существует, то есть вершины s и t принадлежат одной компоненте связности. Веса (стоимости), приписанные ребрам, могут быть положительными, отрицательными или нулями. Единственное ограничение состоит в том, чтобы в графе не было циклов с суммарным отрицательным весом. Если такой цикл все же существует и u - некоторая его вершина, то, двигаясь от s к u, обходя затем этот цикл достаточно большое число раз и попадая наконец в t, получим путь со сколь угодно малым весом. Таким образом, в этом случае кратчайшего пути не существует.

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

1.8.1 Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайшие пути от заданной начальной вершины v_begin до всех остальных вершин графа. Основная идея этого алгоритма: на каждом шаге пытаемся уменьшить кратчайшее расстояние до непросмотренных вершин, используя очередную вершину, длину пути к которой уменьшить уже нельзя. А именно: допустим, что кратчайший путь от вершины v_begin к некоторой вершине u графа G проходит через промежуточную вершину y. Очевидно, что этот путь должен содержать кратчайший путь от v_begin к y, так как в противном случае можно было бы уменьшить длину пути от v_begin к u за счет выбора более короткого пути от v_begin к y. Таким образом, сначала надо найти кратчайший путь к вершине y.

Для достижения этой цели определяется множество непросмотренных вершин. Первоначально в нем содержатся все вершины графа, кроме начальной. На каждом шаге из этого множества выбирается та из вершин, расстояние до которой от начальной меньше, чем для других оставшихся вершин. Текущие кратчайшие расстояния от v_begin до соответствующей вершины хранятся в массиве Distance. Далее пробуем с помощью ребер выбранной вершины v_min уменьшить длину пути до оставшихся непросмотренными вершин. Если это удается, то массив Distance корректируется. Алгоритм Дейкстры также использует массив parent, который содержит номера вершин - элемент parent[k] есть номер предпоследней вершины на текущем кратчайшем пути из начальной вершины в k-ю.

1.8.2 Кратчайшие пути между всеми парами вершин

Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, u) такого пути от вершины v в вершину u, что его длина будет минимальна среди всех возможных путей от v к u. Эта задача может возникнуть, например, если имеется компьютерная сеть и известно время прохождения сетевого пакета между соседними компьютерами. Требуется узнать время прохождения пакета от каждого компьютера к каждому или максимальный временной интервал для прохождения пакета. Или, допустим, дан взвешенный орграф, который содержит время полета по маршрутам, связывающим определенные города, и необходимо построить таблицу, где приводилось бы минимальное время перелета из одного города в любой другой. Подобные задачи можно решить, последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве начальной. Но существует прямой способ решения, использующий алгоритм Флойда-Уоршелла.

1.8.3 Алгоритм Флойда-Уоршелла

Алгоритм Флойда (или Флойда-Уоршелла, Floyd-Warshall) позволяет найти кратчайшее расстояние между любыми двумя вершинами в графе, при этом веса ребер могут быть как положительными, так и отрицательными.

Пусть дан взвешенный ориентированный граф G(V,E). Будем считать, что в графе n вершин, пронумерованных числами от 0 до n-1. Граф задан матрицей смежности, вес ребра i - j хранится в w_ij. При отсутствии ребра i - j значение w_ij=+?, также будем считать, что w_ii=0. Пусть значение равно длине кратчайшего пути из вершины i в вершину j, при этом путь может заходить в промежуточные вершины только с номерами меньшими k (не считая начала и конца пути). То есть - это длина кратчайшего пути из i в j, который вообще не содержит промежуточных вершин, то есть состоит только из одного ребра i - j, поэтому . Значение равно длине кратчайшего пути, который может проходить через промежуточную вершину с номером 0, путь с весом может проходить через промежуточные вершины с номерами 0 и 1 и так далее. Путь с весом может проходить через любые промежуточные вершины, поэтому значение равно длине кратчайшего пути из в может проходить через любые промежуточные вершины, поэтому значение равно длине кратчайшего пути из i в j.

Алгоритм Флойда последовательно вычисляет , , , …, , увеличивая значение параметра k. Начальное значение - .

Теперь предполагая, что известны значения вычислим . Кратчайший путь из вершины i в вершину j, проходящий через вершины с номерами, меньшими, чем k может либо содержать, либо не содержать вершину с номером k-1. Если он не содержит вершину с номером k-1, то вес этого пути совпадает с . Если же он содержит вершину k-1, то этот путь разбивается на две части: i - (k-1) и (k-1) - j. Каждая из этих частей содержит промежуточные вершины только с номерами, меньшими k-1, поэтому вес такого пути равен . Из двух рассматриваемых вариантов необходимо выбрать вариант наименьшей стоимости, поэтому:

(1.8)

То есть основная идея алгоритма заключается в следующем. Пусть есть три вершины i, j, k (рисунок 7) и заданы расстояния между ними. Если выполняется неравенство A[i,k]+A[k,j]<A[i,j], то целесообразно заменить путь i>j путем i>k>j. Такая замена выполняется систематически в процессе выполнения данного алгоритма.

Рисунок 7 - Процесс выполнения алгоритма

Алгоритм Флойда делает n итераций, после i -й итерации матрица А будет содержать длины кратчайших путей между любыми двумя парами вершин при условии, что эти пути проходят через вершины от первой до i. На каждой итерации перебираются все пары вершин и путь между ними сокращается при помощи i вершины.

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

1.9 Математическое моделирование графов

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

1.9.1 Алгоритм Флойда - Уоршела в MATLAB

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

В этом алгоритме строится матрица кратчайших путей между всеми парами вершин орграфа. На входе нужно задать матрицу D размера пп, в каждом элементе которой d находится вес дуги - длина пути из v_i в v_j. При этом диагональные элементы должны быть равны бесконечности: для любого d_ii . Весь алгоритм умещается в тройной цикл. Вот так он выглядит в синтаксисе МАТLАВ:

for j=1:n do, for i=setdiff([1:n],j) do, for k=setdiff([1:n],j) do, D(i,k)=min(D(i,k),D(i,j)+D(j,k)); end end

end

Смысл этого тройного цикла показан на Рисунке 8: для каждой промежуточной вершины v₁ мы проверяем все возможные начальные вершины v_i и конечные v_k , не совпадающие с v₁, но, возможно, совпадающие между собой. Если при каждой такой проверке сумма весов дуг d_ij d_jk окажется меньше d_ik , мы заменяем более длинный путь d_ik более коротким d_ij d_jk . Эта операция называется операцией треугольника.

Рисунок 8 - Операция треугольника

Описание процедуры ShortPath.

Рассмотрим реализацию алгоритма Флойда-Уоршелла на МАТLАВ. На вход подается список дуг размером m2 или m3 (идентификатор E). Если задано два столбца, то решается невзвешенная задача и ищется путь из минимального количества дуг, а если три - то взвешенная, и в этом случае ищутся пути минимального общего веса. На выходе процедура возвращает матрицу кратчайших путей размера nn. Заголовок процедуры ShortPath и справочная информация к ней имеют вид:

function dSP=ShortPath(E)% Функция dSP=ShortPath(E) решает задачу о кратчайшем пути

% между всеми вершинами орграфа.

% Входной параметр

% Е(m,2) или (m,3) - дуги орграфа и их веса;

% 1-й и 2-й элементы каждой строки - это номера вершин;

% 3-й элемент каждой строки - это вес дуги; % m - количество дуг.

% Если задан массив Е(m,2) , то все веса равны 1.

% Выходной параметр:

% dSP(n,n) - матрица кратчайших путей

% Каждый элемент dSP(i,j) - это кратчайший путь

% из вершины i в вершину j (может быть inf,

% если вершина j не достижима из вершины i).

% Используется алгоритм Флойда-Уоршелла.

Процедура ShortPath проверяет исходные данные: наличие данных, размерность и количество столбцов входного массива, положительность и целочисленность первых двух столбцов. Для запуска алгоритма Флойда-Уоршелла нужно задать матрицу весов дуг размером nn. Если какой-либо дуги нет, в соответствующем элементе записывается бесконечное число.

Описание процедуры PlotGraph.

Процедура РlоtGгарh предназначена для рисования графов (в том числе мультиграфов и псевдографов) и орграфов. Процедура РlоtGгарh имеет следующий порядок вызова, входные и выходные аргументы:

Function h=РlоtGгарh(V,Е,р)

% Функция h=РlоtGгарh(V,Е,р) рисует граф (орграф).

% Входные параметры:

% V(n,2) или (n,3) - координаты вершин

% (1-й столбец - х, 2-й - у) и, может быть, 3-й - веса;

% n - количество вершин;

% если V(n,2), рисуются номера вершин,

% если V(n,3) , рисуются веса вершин.

% Е(m,2) или (m,3) - ребра графа (дуги орграфа) и их веса;

% 1-й и 2-й элементы каждой строки - это номера вершин;

% 3-й элемент каждой строки - это вес дуги;

% m - количество дуг.

% если Е(m,2) , рисуются номера ребер (дуг);

% если Е (т,3) , рисуются веса ребер (дуг);

% для графа без ребер задаем Е=[0];

% р = 'g' (рисовать граф) или 'о' (рисовать орграф);

%(необязательный параметр, по умолчанию 'g') .

% Выходной параметр:

% h - дескриптор фигуры.

Номера всех вершин в массиве E должны быть целыми положительными числами. Размер массива V должен быть совместим с номерами вершин в массиве E.

1.9.2 Работа с графами в системе Maple

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

Граф задается оператором graph (V,E), где V - множество вершин графа, E - множество ребер.

V:={1, 2, 3,…,n}

Или

V:{seg(i, i=1..n)}

Для задания графа можно использовать операторы new(G), addvertex, addedge.

оператор вывода рисунков на печать имеет три варианта вывода вершин: например, Concentric, Linear и по умолчанию, равномерно по окружности. Если в опции Concentric ([1,2,3],[4,5,6,7]), то вершины первого списка будут на внутренней окружности. Аналогично выводятся вершины графов с опцией Linear.

Оператор print (j) выводит результат на экран.

В Maple допускается русский шрифт для переменных.

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

1.9.3 Представление графов в системе Mathematica

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

После загрузки пакета можно работать с теми функциями, которые в нем используются. Чтобы изобразить граф, необходимо задать множество ребер и вершин. Например, сформируем множество вершин v и множество ребер e будущего графа G (Рисунок 8).

Рисунок 8 - Формирование вершин и ребер графа

Задать граф можно с помощью следующих функций:

FromUnorderedPairs[e, v] - задает неориентированный граф, где e - множество ребер, v - множество вершин.

FromOrderedPairs[e, v] - задает ориентированный граф, где e - множество ребер, v - множество вершин. На рисунке 9 приведен пример задания неориентированного графа G на основе множеств е и v.

Ячейка вывода показывает, что G - неориентированный граф (Undirected) с восьмью ребрами (число «8») и девятью вершинами (число «9»).

С помощью функции ShowGraph изображается граф. Функция задается следующим образом ShowGraph[G], где G - граф, также могут быть указаны параметры графа G.



Рисунок 9 - Формирование графа.

1.10 Оценка сложности алгоритмов

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

Анализ алгоритмов проводят на модели абстрактного вычислителя, называемого машиной с произвольным доступом к памяти (RAM):

- память состоит из ячеек, каждая из которых имеет адрес и может хранить один элемент данных;

- каждое обращение к памяти занимает одну единицу времени, независимо от номера адресуемой ячейки;

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

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

- циклы и функции не считаются элементарными операциями.

1.11 Сравнение с другими алгоритмами

Алгоритм Флойда-Уоршелла является эффективным для расчета всех кратчайших путей в плотных графах, когда имеет место большое количество пар ребер между парами вершин. В случае разреженных графов с ребрами неотрицательного веса лучшим выбором считается использование алгоритма Дейкстры для каждого возможного узла. При таком выборе сложность составляет при применении двоичной кучи, что лучше, чем алгоритма Флойда - Уоршелла тогда, когда существенно меньше (условие разреженности графа). Если граф разрежен, у него имеются ребра с отрицательным весом и отсутствуют циклы с отрицательным суммарным весом, то используется алгоритм Джонсона, который имеет ту же сложность, что и вариант с алгоритмом Дейкстры.

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

2. АЛГОРИТМИЧЕСКАЯ ЧАСТЬ

2.1 Реализация алгоритма Флойда-Уоршелла без вычислительной системы

Определим длины минимальных путей между любыми парами вершин орграфа G(V,E) (Рисунок10).

Рисунок 10 - Орграф G(V,E)

Сформируем матрицу смежности D[i,j] орграфа G (Таблица 2).

Таблица 2 - матрица смежности D[i,j] орграфа G.

	v1	v2	v3	v4	v5	v6
v1	0	?	5	5	2	12
v2	?	0	?	?	?	2
v3	?	2	0	?	?	?
v4	?	2	?	0	?	?
v5	?	?	1	2	0	?
v6	?	?	?	?	?	0

2.1.1 Описание общего алгоритма решения поставленной задачи

По сформированной матрице смежности D[i,j] орграфа G необходимо найти расстояния между всеми парами вершин D[i,j] = d(v_i,v_j). Общий алгоритм решения задачи:

1. Для всех i = 1,…,n, j = 1,…,n положим D[i,j] = c_ij .

2. Для всех i = 1,…,n положим D[i,i] = 0.

3. Положим m = 1.

4. Положим i = 1.

5. Положим j = 1.

6. D[i,j] = min (D[i,j], D[i,m] + D[m,j]).

7. Если j < n, то положим j = j + 1 и переходим к шагу 6.

8. Если i < n, то положим i = i + 1 и переходим к шагу 5.

9. Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D[i,j] дают расстояния между вершинами v_i и v_j.

2.1.2 Ручной расчет задачи и вычислений

Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения (Таблица 3), так как

D[i,j] = min (D[i,j], D[i,m] + D[m,j]) (2.4)

Таблица 3 - Элементы матрицы D[i,j] при m=1

	v1	v2	v3	v4	v5	v6
v1	0	?	5	5	2	12
v2	?	0	?	?	?	2
v3	?	2	0	?	?	?
v4	?	2	?	0	?	?
v5	?	?	1	2	0	?
v6	?	?	?	?	?	0

Если i=j, то все элементы главной диагонали матрицы D[i,j] равны нулю.

Рассмотрим случай, когда i = 2, а j = 3 (m=3). Тогда по (2.4) получим

D[2,3] = min (D[2,3], D[2,1] + D[1,3]) = min (,+5) = .

Матрица примет вид, приведенный в таблице 4.

Таблица 4 - Элементы матрицы при m=3

	v1	v2	v3	v4	v5	v6
v1	0	?	5	5	2	12
v2	?	0	?	?	?	2
v3	?	2	0	?	?	4
v4	?	2	?	0	?	4
v5	?	?	1	2	0	?
v6	?	?	?	?	?	0

Далее, при j = 4 (то есть m=4) по формуле (2.4) получим

D[2,4] = min(D[2,4], D[2,1] + D[1,4]) = min (,+5) = .

А матрица примет вид, приведенный в таблице 5.

Таблица 5 - Элементы матрицы при m=4

	v1	v2	v3	v4	v5	v6
v1	0	7	5	5	2	9
v2	?	0	?	?	?	2
v3	?	2	0	?	?	4
v4	?	2	?	0	?	4
v5	?	3	1	2	0	5
v6	?	?	?	?	?	0

Продолжаем процесс до тех пор, пока i 6 и j 6 (Таблицы 6 и 7).

Таблица 6 - Элементы матрицы при m=5

	v1	v2	v3	v4	v5	v6
v1	0	7	5	5	2	9
v2	?	0	?	?	?	2
v3	?	2	0	?	?	4
v4	?	2	?	0	?	4
v5	?	3	1	2	0	5
v6	?	?	?	?	?	0

Таблица 7 - Элементы матрицы при m=6

	v1	v2	v3	v4	v5	v6
v1	0	5	3	4	2	7
v2	?	0	?	?	?	2
v3	?	2	0	?	?	4
v4	?	2	?	0	?	4
v5	?	3	1	2	0	5
v6	?	?	?	?	?	0

Конечный результат вычислений представлен в таблице 7.

Таблица 8 - Конечный результат вычислений

	v1	v2	v3	v4	v5	v6
v1	0	5	3	4	2	7
v2	?	0	?	?	?	2
v3	?	2	0	?	?	4
v4	?	2	?	0	?	4
v5	?	3	1	2	0	5
v6	?	?	?	?	?	0

2.2 Построение алгоритма для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа в среде MATLAB

В качестве исходного зададим ориентированный граф с 11 вершинами и 22 ребрами. Введем веса дуг. Нарисуем заданный орграф, используя функцию PlotGraph. Используя процедуру ShortPath, для заданного орграфа найдем матрицу кратчайших путей.

2.2.1 Использование процедуры PlotGraph

Листинг программы:

clear all

V=[[0 0];[1 1];[1 0];[1 -1];...

[2 1];[2 0];[2 -1];[3 1];...

[3 0];[3 -1];[4 0]]; % координаты вершин

E=[[1 2 5];[1 3 5];[1 4 5];[2 3 2];[3 4 2];[2 5 3];...

[2 6 2];[3 6 5];[3 7 2];[4 7 3];[6 5 1];[6 7 1];...

[5 8 5];[6 8 2];[6 9 3];[7 9 2];[7 10 3];[8 9 2];...

[9 10 2];[8 11 5];[9 11 4];[10 11 4]]; % ребра и их веса

gplot(V,E,'o'); % рисуем орграф

set(get(gcf,'CurrentAxes'),...

'FontName','Times New Roman Cyr','FontSize',14)

title('\bfИсходный орграф со взвешенными дугами')

Исходный орграф, нарисованный с помощью MATLAB представлен на Рисунке 11.

Страница:

•  1 
•  2 

курсовая работа "Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла" скачать

Подобные документы

• Алгоритмы на графах. Нахождение кратчайшего пути

  Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
  
  курсовая работа [2,4 M], добавлен 08.10.2014
  

• Поиск кратчайшего пути между парами вершин в ориентированном и неориентированном графах путем использования алгоритма Флойда

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

• Построение эйлерова цикла. Алгоритм Форда и Уоршелла

  Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда.
  
  реферат [108,4 K], добавлен 01.12.2008
  

• Теория графов

  Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
  
  дипломная работа [145,5 K], добавлен 19.07.2011
  

• Алгоритм Форда-Беллмана

  Основные понятия теории графов. Матричные способы задания графов. Выбор алгоритма Форда–Бэллмана для решения задачи поиска минимальных путей (маршрутов) в любую достижимую вершину нагруженного орграфа. Способы выделения пути с наименьшим числом дуг.
  
  курсовая работа [109,1 K], добавлен 22.01.2016
  

• Деревья и их свойства (частный вид графов)

  Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
  
  реферат [131,8 K], добавлен 11.11.2008
  

• Элементы теории графов

  Основные понятия теории графов. Степень вершины. Маршруты, цепи, циклы. Связность и свойства ориентированных и плоских графов, алгоритм их распознавания, изоморфизм. Операции над ними. Обзор способов задания графов. Эйлеровый и гамильтоновый циклы.
  
  презентация [430,0 K], добавлен 19.11.2013
  

• Орграфы, теория и применение

  Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов.
  
  реферат [220,4 K], добавлен 22.11.2010
  

• Алгоритм Дейкстры

  Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
  
  контрольная работа [466,3 K], добавлен 11.03.2011
  

• Спектр графа

  Спектральная теория графов. Теоремы теории матриц и их применение к исследованию спектров графов. Определение и спектр предфрактального фрактального графов с затравкой регулярной степени. Связи между спектральными и структурными свойствами графов.
  
  дипломная работа [272,5 K], добавлен 05.06.2014
  

• Основные понятия теории графов

  Общее понятие, основные свойства и закономерности графов. Задача о Кенигсбергских мостах. Свойства отношения достижимости в графах. Связность и компонента связности графов. Соотношение между количеством вершин связного плоского графа, формула Эйлера.
  
  презентация [150,3 K], добавлен 16.01.2015
  

• Эйлеровы графы

  Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке.
  
  курсовая работа [1006,8 K], добавлен 23.12.2007
  

• Алгоритмы на графах

  Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину.
  
  презентация [36,1 K], добавлен 16.09.2013
  

• Операции на графах

  Операции на графах позволяют образовывать новые графы из нескольких более простых. Операции на графах без параллельных ребер. Объединение графов. Свойства операции объединения т, которые следуют из определения операции и свойств операций на множествах.
  
  реферат [106,0 K], добавлен 27.11.2008
  

• Метод кратчайшего пути

  Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
  
  курсовая работа [1,0 M], добавлен 26.09.2013
  

• Теория графов. Описание графов. Алгоритм Прима-Краскала

  Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
  
  курсовая работа [625,4 K], добавлен 30.09.2014
  

• Графы. Основные понятия

  Восстановление графов по заданным матрицам смежности вершин. Построение для каждого графа матрицы смежности ребер, инцидентности, достижимости, контрдостижимости. Поиск композиции графов. Определение локальных степеней вершин графа. Поиск базы графов.
  
  лабораторная работа [85,5 K], добавлен 09.01.2009
  

• Элементы теории графов

  Теория графов как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Основные понятия теории графов. Матрицы смежности и инцидентности и их практическое применение при анализе решений.
  
  реферат [368,2 K], добавлен 13.06.2011
  

• Решение задач с применением теории графов

  Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
  
  курсовая работа [1,8 M], добавлен 18.01.2013
  

• Практическое применение теоремы Пойа и перечисления графов

  Основополагающие понятия теории графов. Определение эквивалентности, порождаемое группой подстановок, и доказательство леммы Бернсайда о числе ее классов. Понятие перечня конфигурации и доказательство теоремы Пойа. Решение задачи о перечислении графов.
  
  курсовая работа [649,2 K], добавлен 18.01.2014
  

Другие документы, подобные "Поиск кратчайшего пути. Алгоритм Флойда-Уоршелла"

• главная
• рубрики
• по алфавиту
• вернуться в начало страницы
• вернуться к началу текста
• вернуться к подобным работам