Кратчайшие пути между всеми парами вершин графа. Алгоритм Флойда

Оглавление
Введение……………………………………………………………………………3
Алгоритм Флойда………………………………………………………………….4
Пример решения задачи……………………………………………………………7
Выводы……………………………………………………………………………..11
Список использованной литературы……………………………………………..12

Введение
В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Математические модели в виде графов широко используются при моделировании разнообразных явлений, процессов и систем. Многие теоретические и реальные прикладные задачи могут быть решены при помощи тех или иных процедур анализа графовых моделей. В качестве примера можно привести задачу составления маршрута движения транспорта между различными городами при заданном расстоянии между населенными пунктами.
В данной работе рассматривается алгоритм Флойда — Уоршелла — алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом.
Алгоритм Флойда

Кратчайшим путем между парой вершин называется такой путь между ними, что сумма весов ребер, входящих в данный путь минимальна.
Заметим, что между некоторыми вершинами может и не быть кратчайшего пути. Это возможно, если между ними существует путь содержащий цикл отрицательного веса. Проходя по этому циклу мы можем неограниченно уменьшать общий вес цепи.
Если же кратчайший путь существует, то существует и простой кратчайший путь, соединяющий данные вершины (например, если из исходного выбросить все циклы нулевой длины).
Многие задачи сводятся к поиску кратчайших путей. Обычно рассматривается следующая задача: дан граф, у которого веса ребер – неотрицательные числа, требуется найти кратчайший путь между парой вершин. Она решается с помощью алгоритма Дейкстры. Если граф может содержать ребра отрицательного веса, то применяется алгоритм Форда-Беллмана. Он так же позволяет определить, существует ли в графе отрицательный цикл. Если требуется найти кратчайшие пути между всеми парами вершин, то применяется алгоритм Флойда-Уоршелла.
Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В алгоритме сеть представлена в виде квадратной матрицы с n строками и nстолбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.
Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 1). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.
Рис.1. Треугольный оператор
    Алгоритм Флойда требует выполнения следующих действий.
    Шаг 0. Определяем начальную матрицу расстояния D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:
Рис.2. Начальная ситуация    Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство dik + dkj < dij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:
создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dik + dkj,
создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k = k + 1 и повторяем шаг k.
    Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу Dk-1 так, как она показана на рисунке 3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:
Рис.3. Иллюстрация алгоритма Флойда    После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и jвыполняется по следующим правилам.
Расстояние между узлами i и j равно элементу dij в матрице Dn.
Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i -> k -> j. Если далее sik = k и skj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.
Пример решения задачи
Пример. Найдем для сети, показанной на рисунке 4, кратчайшие пути между любыми двумя узлами. Расстояние между узлами этой сети проставлены на рисунке возле соответствующих ребер. Ребро (3, 5) ориентированно, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:
Рис.4. Пример сети
    Шаг 0. Начальные матрицы D0 и S0 строятся непосредственно по заданной схеме сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d53 равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:
Рис.5. Начальное состояние    Шаг 1. В матрице D0 выделены ведущие строка и столбец (k = 1). Двойной рамкой представлены элементы d23 и d32, единственные среди элементов матрицы D0, значения которых можно улучшить с помощью треугольного оператора. Таким образом, чтобы на основе матриц D0 и S0 получить матрицы D1 и S1, выполняем следующие действия.
Заменяем d23 на d21 + d13 = 3 + 10 = 13 и устанавливаем s23 = 1.
Заменяем d32 на d31 + d12 = 10 + 3 = 13 и устанавливаем s32 = 1.
    Матрицы D1 и S1 имеют следующий вид:
Рис.6. Матрицы D1 и S1
    Шаг 2. Полагаем k = 2; в матрице D1 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D1 и S1, выделенным двойной рамкой. В результате получаем матрицы D2 и S2:
Рис.7. Матрицы D2 и S2
    Шаг 3. Полагаем k = 3; в матрице D2 выделены ведущие строка и столбец. Треугольный оператор применяется к элементам матрицы D2 и S2, выделенным двойной рамкой. В результате получаем матрицы D3 и S3:
Рис.8. Матрицы D3 и S3
    Шаг 4. Полагаем k = 4, ведущие строка и столбец в матрице D3 выделены. Получаем новые матрицы D4 и S4:
Рис.9. Матрицы D4 и S4
    Шаг 5. Полагаем k = 5, ведущие строка и столбец в матрице D4 выделены. Никаких действий на этом шаге не выполняем; вычисления закончены.
    Конечные матрицы D4 и S4 содержат всю информацию, необходимую для определения кратчайших путей между любыми двумя узлами сети. Например, кратчайшее расстояние между узлами 1 и 5 равно d15 = 12.
    Для нахождения соответствующих маршрутов напомним, что сегмент маршрута (i, j) состоит из ребра (i, j) только в том случае, когда sij = j. В противном случае узлы i и j связаны, по крайней мере, через один промежуточный узел. Например, поскольку s15 = 4 и s45 = 5, сначала кратчайший маршрут между узлами 1 и 5 будет иметь вид 1->4->5. Но так как s14 не равно 4, узлы 1 и 4 в определенном пути не связаны одним ребром (но в исходной сети они могут быть связаны непосредственно). Далее следует определить промежуточный узел (узлы) между первым и четвертым узлами. Имеем s14 = 2 и s24 = 4, поэтому маршрут 1->4 заменяем 1->2->4. Поскольку s12 = 2 и s24 = 4, других промежуточных узлов нет. Комбинируя определенные сегменты маршрута, окончательно получаем следующий кратчайший путь от узла 1 до узла 5: 1->2->4->5. Длина этого пути равна 12 километрам.
Выводы
В рамках теории исследования операций рассматривается большое количество практических задач, которые можно сформулировать и решить как сетевые модели. Например, проектирование газопровода, соединяющего буровые скважины морского базирования с находящейся на берегу приемной станцией; нахождение кратчайшего маршрута между двумя городами по существующей сети дорог и мнегие другие. Решение приведенных задач (как и многих других подобных задач) требует применения различных сетевых оптимизационных алгоритмов. Мною в данной работе был рассмотрен алгоритм Флойда.
Список использованной литературы
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс», 2006. — С. 1296. 
Белоусов А. И., Ткачев С. Б. Дискретная математика. — М.: МГТУ, 2006. — 744 с. 
Степанов В.Н. Дискретная математика: графы и алгоритмы на графах. — Омск: ОмГТУ, 2010. — 120 с.