DO Lektsia 5

Кратчайшие пути между всеми парами вершин
Алгоритм Уоршалла
Пусть A - матрица смежностей ориентированного графа.
Метод определения матрицы достижимости P вначале путем вычисления A1, A2, ..., An, а затем Bn является очень громоздким.
Более эффективный метод - использование в вычислениях булевские матричные операции.
Матрица смежностей, так же как и матрица достижимости, является булевской матрицей. Заметим, что A(A(r-1)=A(r) для любого r=2,3,...
Здесь A(r) является булевской матрицей, и элемент на пересечении i-й строки и j-го столбца A(r) = 1 в том случае, когда существует по крайней мере один путь длины r из vi в vj, при любом целом положительном r.
Из этих рассуждений понятно, что матрица достижимости P задается выражением
[ Cкачайте файл, чтобы посмотреть картинку ]
Например, если
[ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Описанный метод получения матрицы достижимости ориентированного графа называется алгоритмом Уоршалла [Warshall,1962], этот алгоритм обрабатывает матрицу по столбцам.
Уоррен [Свами,Тхуласираман,1984,с.320] предложил двухпроходной "строко-ориентированный" алгоритм, в котором при обработке i-ой вершины в первом проходе обрабатываются только ребра, связанные с вершинами, меньшими i, а во втором проходе - только ребра, связанные с вершинами, большими i.
Другими словами, алгоритм преобразует матрицу смежности графа G в матрицу достижимости, обрабатывая в первом проходе только элементы матрицы, расположенные ниже ее главной диагонали, а во втором проходе - только элементы матрицы, расположенные выше ее главной диагонали.
Таким образом, при каждом проходе обрабатывается не более n(n-1)/2 ребер.
Применение алгоритма Уоршалла
Алгоритм Уоршалла может быть модифицирован с целью получения матрицы, содержащей длины кратчайших путей между вершинами [Трамбле, Соренсон, 1982].
Опишем алгоритм [Липский, 1988]
Обозначим через d(m)ij длину кратчайшего из путей из vi в vj с промежуточными вершинами из множества {v1,...,vm}.
Тогда имеем следующие уравнения:
[ Cкачайте файл, чтобы посмотреть картинку ]
Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из vi в vj c промежуточными вершинами из множества {v1,...,vm,vm+1}.
Если этот путь не содержит vm+1, то разделив путь на отрезки от vi до vm+1 и от vm+1 до vj, получаем равенство:
d(m+1)ij=d(m)im+d(m)mj.
Соотношения позволяют вычислить расстояния d(vi,vj)=d(n)ij.
Авторами приведенного алгоритма являются Уоршалл и Р.Флойд (Floyd R.W.).

Алгоритм Флойда - поиск всех кратчайших путей в графе
Алгоритма Дейкстры позволяет при доведении до конца построить ориентированное дерево кратчайших путей от некоторой вершины.
Метод Флойда позволяет найти длины всех кратчайших путей в графе.
Таким образом, метод Флойда может быть решен многократным применением алгоритма Дейкстры (каждый раз последовательно выбираем вершину от первой до N-ной, пока не получим кратчайшие пути от всех вершин графа), однако реализация подобной процедуры потребовала бы значительных вычислительных затрат.
Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину.
Пусть вершины графа пронумерованы от 1 до n и введено обозначение [ Cкачайте файл, чтобы посмотреть картинку ] для длины кратчайшего пути от i до j.
Очевидно, что [ Cкачайте файл, чтобы посмотреть картинку ]  длина (вес) ребра (i, j), если таковое существует (в противном случае его длина может быть обозначена как ().
Существует два варианта значения [ Cкачайте файл, чтобы посмотреть картинку ]:
Кратчайший путь между i, j  не проходит через вершину k, тогда [ Cкачайте файл, чтобы посмотреть картинку ]
Существует более короткий путь между i, j  , проходящий через k, тогда он сначала идёт от i до k, а потом от k до j. В этом случае, очевидно, [ Cкачайте файл, чтобы посмотреть картинку ]
Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений.
Тогда рекуррентная формула имеет вид: [ Cкачайте файл, чтобы посмотреть картинку ]  длина ребра [ Cкачайте файл, чтобы посмотреть картинку ]
[ Cкачайте файл, чтобы посмотреть картинку ]
Алгоритм Флойда-Уоршелла последовательно вычисляет все значения [ Cкачайте файл, чтобы посмотреть картинку ]  для k от 1 до n. Полученные значения являются длинами кратчайших путей между вершинами  i, j.

Очевидно, что сложность алгоритма есть O(n3). В монографии [Липский,1988] отмечено, что "для общего случая (т.е. без предположения о неотрицательности весов или о бесконтурности графа) не известен ни один алгоритм нахождения расстояния между одной фиксированной парой вершин, который был бы значительно эффективнее алгоритма нахождения расстояний между всеми парами вершин."

Замечание
Если в графе есть циклы отрицательного веса, то формально алгоритм Флойда-Уоршелла неприменим к такому графу.
На самом же деле, для тех пар вершин i и j, между которыми нельзя зайти в цикл отрицательного веса, алгоритм отработает корректно.
Для тех же пар вершин, ответа для которых не существует (по причине наличия отрицательного цикла на пути между ними), алгоритм Флойда найдёт в качестве ответа какое-то число (возможно, сильно отрицательное, но не обязательно).
Тем не менее, можно улучшить алгоритм Флойда, чтобы он аккуратно обрабатывал такие пары вершин и выводил для них - (.
Для этого можно сделать, например, следующий критерий "не существования пути".
Итак, пусть на данном графе отработал обычный алгоритм Флойда.
Тогда между вершинами  i и j не существует кратчайшего пути тогда и только тогда, когда найдётся такая вершина t, достижимая из i и из которой достижима j, для которой выполняется
[ Cкачайте файл, чтобы посмотреть картинку ].
Кроме того, при использовании алгоритма Флойда для графов с отрицательными циклами следует помнить, что возникающие в процессе работы расстояния могут сильно уходить в минус, экспоненциально с каждой фазой.
Поэтому следует принять меры против целочисленного переполнения, ограничив все расстояния снизу какой-нибудь величиной/

Применение
Как и любой базовый алгоритм, алгоритм Флойда Уоршелла используется очень широко и много где, начиная от поиска транзитивного замыкания графа, заканчивая генетикой и управлением проектами: транспортные и другие сети. Транспортная система города - это граф, соответственно присвоив каждому ребру некую стоимость, рассчитанную из пропускной способности и других важный параметров можно найти по самый короткий/быстрый/дешевый путь.

Пример
[ Cкачайте файл, чтобы посмотреть картинку ]
Найдем для сети кратчайшие пути между любыми двумя узлами. Ребро (3, 5) ориентировано, поэтому не допускается движение от узла 5 к узлу 3. Все остальные ребра допускают движение в обе стороны:
Шаг 0. Начальные матрицы D0 и S0 строятся непосредственно по заданной схеме сети. Матрица D0 симметрична, за исключением пары элементов d35 и d53, где d53 равно бесконечности, поскольку невозможен переход от узла 5 к узлу 3:
[ Cкачайте файл, чтобы посмотреть картинку ]
Шаг 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 имеют следующий вид:
[ Cкачайте файл, чтобы посмотреть картинку ]
Шаг 2. Полагаем k = 2; оператор применяем к элементам матрицы D1 и S1. В результате получаем матрицы D2 и S2:
[ Cкачайте файл, чтобы посмотреть картинку ]
Шаг 3. Полагаем k = 3; получаем матрицы D3 и S3:
[ Cкачайте файл, чтобы посмотреть картинку ]
Шаг 4. Полагаем k = 4, получаем новые матрицы D4 и S4:
[ Cкачайте файл, чтобы посмотреть картинку ]
Шаг 5. Полагаем k = 5, вычисления закончены.
Конечные матрицы 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 километрам.


Контуры в ориентированных графах
Одной из важнейших задач, связанных с контурами, является задача нахождения множества всех контуров.
Количество контуров ориентированного графа может быть экспоненциально большим относительно количества вершин. Поэтому при разработке алгоритмов внимание обращается не на полную трудоемкость алгоритма, а на относительную, т.е. на трудоемкость, приходящуюся на один контур.
Рассмотрим сейчас алгоритм отыскания множества вершин, принадлежащих контуру заданной длины [Евстигнеев, 1985].
Алгоритм использует матрицу смежности A и матрицу Ak, если длина контура равна k.
Выберем некоторое i, такое, что aii(k)=1. Это означает, что вершина vi принадлежит контуру длины k. Тогда вершина vj принадлежит тому же контуру, если выполняются следующие три условия:
ajj(k)=1;
существует n для которого aij(n)=1, т.е. существует путь длины n из vi в vj;
aji(k-n)=1, т.е. существует путь длины k-n из vj в vi.
Таким образом, для каждой вершины i графа можно построить множество вершин, каждый элемент которого принадлежит некоторому контуру длины k.









ДО_Лекция _5

13 PAGE \* MERGEFORMAT 14115







Приложенные файлы

  • doc 18813921
    Размер файла: 407 kB Загрузок: 0

Добавить комментарий