Графовые алгоритмы

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

Его описание приводится ниже при помощи алгоритмической схемы. Идентификаторы D w - рабочий массив, при вычислениях интерпретируется как кратчайшая длина из вершины w в вершину z. w?X. d s, t - массив длин ребер графа для каждой пары вершин s, t ?X. Если некоторое ребро отсутствует, то в элементе этого массива полагается записанным некоторое достаточно большое число, превышающее сумму длин всех ребер графа Stack - последовательность вершин, определяющая кратчайший путь из x в z. Begin Stack Очистить Stack. Stack z Поместить в стек конечную вершину z. w z Запомнить первую пройденную вершину.

D z 0 Обнуление длины пути из вершины z в нее же. While w x do Пока не будет достигнута начальная вершина, выполнять перебор вершин графа p вершина, для которой величина D p d p, w D w минимальна.

Если таких вершин несколько и среди них имеется вершина x, то p x, если же среди них нет вершины x - взять любую из доставляющих минимум сумме. Stack p Записать выбранную вершину в стек. w p и взять ее для построения следующего шага. End End. Пусть число вершин графа X n, а число ребер U m. Оценим сложность этого алгоритма как число шагов выполнения алгоритмической схемы, считая одним шагом выполнение ровно одного выполнимого оператора, каковые представлены только строками 2,3,4,5,6,8,9. В худшем случае выбор вершины в строке 8 по минимуму расстояния произойдет в результате просмотра всех n вершин, а цикл с заголовком в строке 6 повторится для всех вершин, поэтому сложность алгоритма можно оценить как C n 2, где С - некоторая константа, учитывающая реализацию алгоритма в произвольной вычислительной среде.

Следующий алгоритм обеспечивает нахождение кратчайших расстояний от фиксированной вершины х, называемой источником, до всех остальных вершин графа с ограничением, предполагающим отсутствие в графе контуров отрицательной длины сумма длин ребер, входящих в любой контур, неотрицательна. Алгоритм Форда-Беллмана Идентификаторы d s, t - массив длин ребер графа для каждой пары вершин s, t ?X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число. х - вершина-источник графа X,U . n X - число вершин графа. u, w,k - рабочие переменные.

D w - массив, в котором к концу работы алгоритма будут содержаться кратчайшие длины путей из х в w для всех вершин w ?X. Begin D x 0 Длина пути из источника x. For w ?X do D w d x, w Инициализация матрицы расстояний For k 1 to n-2 do Повторять n-2 раз For w ? X x do Цикл по всем вершинам, кроме источника.

For u ?X do D w min D w ,D u d u, w выбор минимума.

End. Этот алгоритм также основан на соотношении принципе оптимальности Беллмана. Всякий раз, когда находится путь через транзитную вершину u, который короче найденного пути из х в w, он заменяется на более короткий путь. Это соотношение должно проверяться для любой возможной из n-2 транзитных вершин при оценке пути в каждую вершину, поэтому в алгоритме имеется цикл, определенный в строке 4. Алгоритм Дейкстры нахождения кратчайших расстояний от источника до всех остальных вершин применим только тогда, когда граф не имеет контуров или когда веса всех ребер неотрицательны.

Идентификаторы d s, t - массив длин ребер графа для каждой пары вершин s, t ? X. Если ребра нет, то соответствующий элемент этого массива содержит достаточно большое число. х - вершина-источник графа X,U . n X - число вершин графа. u, w - рабочие переменные. D w - массив, в котором к концу работы алгоритма будут содержаться кратчайшие длины путей из x в w для всех вершин w ?X. BEGIN D x 0 For w ?X do D w d x, w T X x While T do Begin w вершина r из T такая, что D r min D p p из T T T w For u ?T do D w min D w ,D u d u, w End END Алгоритм Форда-Фалкерсона нахождения максимального потока в сети. Многие задачи исследования операций сводятся к анализу потоков, маршрутов, последовательностей событий, протекающих со времени, и других процессов, которые можно представить в виде множества взаимосвязанных элементов.

Для математического представления таких процессов удобно их задание в виде графов. Рассмотрим конечный ориентированный граф Г X,u, в котором Х x1, ,xn -множество вершин, U - множество дуг. Пусть x X. Обозначим E x - множество дуг графа, входящих в х, E- x - выходящих из х. Множества начальных вершин дуг из Е х и множество конечных вершин дуг из Е- х обозначим соответственно S x и S- x. E x E- x y x y S x S- x Рис. 3. Окрестность вершины графа.

Граф Г называют транспортной сетью, если каждой дуге u соответствует целое число c u 0 и найдутся x0 и z из Х такие, что Е х0 Е- z. Вершина х0 называется истоком, z-стоком, c u - пропускной способностью дуги. Потоком в транспортной сети называют целочисленную функцию ф u, удовлетворяющую следующим условиям 1 0 ф u с u 2 ф u - ф u 0 для любой вершины x x0, x z. u Е х u Е- х При этом поток не может накапливаться ни в одной вершине транспортной сети, кроме истока х0 и стока z, поэтому ф u ф u Ф. u Е х u Е- х Величину Ф называют потоком транспортной сети. Дуга u называется насыщенной, если ф u c u. Поток Ф называется полным, если каждый путь из х0 в z содержит хотя бы одну насыщенную дугу. Рассмотрим разбиение R множества вершин сети Х Х1UX2, X1?X2 X1?X2 x0?X1, z?X2, называемое разрезом сети. Сумма пропускных способностей множества xi, xj, xi из X1, Xj из Х2 определяет пропускную способность разреза R r R c u, u? xi, xj xi ?X1, xj?X2 Поскольку для любой дуги u выполняется неравенство ф u c u, то Ф r R . Теорема Форда-Фалкерсона максимальный поток в сети равен минимальной величине разрезов в этой сети. Алгоритм нахождения максимального потока, предложенный Фордом и Фалкерсоном, состоит в постепенном увеличении допустимого потока Ф до максимальной величины Ф . Начальное значение потоков полагается равным нулю. Процесс увеличения потока состоит в поиске путей, на которых возможно увеличение потока, с соответствующей разметкой вершин сети. Алгоритм Форда-Фалкерсона Предполагается, что путь из истока в сток с ненулевыми пропускными способностями входящих в него дуг существует.

I. Увеличение потока. 1. Присвоить истоку х0 пометку х0, d x0 . Это означает, что вход в исток не ограничен величина d всегда показывает, на сколько может быть увеличен поток, входящий в помеченную вершину.

Здесь символ обозначает достаточно большое число - начальное значение пометки. 2. Взять некоторую вершину xi с пометкой, которая в общем случае имеет вид или - xk, d xi, где xk - обозначение вершины, d xi - некоторое число.

Каждой непомеченной вершине xj из S- xi, для которой ф xi, xj с xi, xj, присвоить пометку xi, min d xi, c xi, xj -ф xi, xj. Это означает, что поток в дуге xi, xj может быть увеличен знак плюс на величину, определяемую минимумом.

Каждой непомеченной вершине xj из S xi, такой, что ф xj, xi 0 присвоить пометку -xi, min d xi, ф xj, xi, что означает возможность уменьшения потока на величину, определяемую минимумом. 3. Если сток не помечен и можно пометить какую-либо вершину, кроме стока, то перейти к п.2. 4. Если оказался помеченным сток z, и в его пометку входит число d z, то между вершинами x0 и z найдется цепь, все вершины которой помечены номерами предыдущих вершин.

Для каждой помеченной вершины х в этой цепи изменить величину потока ф y, x ф y, x d z, если х имеет пометку y, d x или ф y, x ф y, x -d z, если х имеет пометку -y, d x. Пометка вершины х стирается, назначенные потоки запоминаются.

При достижении в процессе стирания пометок вершин цепи истока х0 перейти к п.1 если же ни одну вершину пометить не удается и сток z не помечен, то перейти к построению разреза.

II.Построение разреза. Искомый минимальный размер R определяется двумя множествами Х1 и Х2, где Х1 - все помеченные вершины, Х2 - вершины, которые не удается пометить. При этом полный поток Ф Ф должен быть равен величине полученного минимального разреза. 2.Сетевые структуры на базе теоретико-графовых моделей 2.1.