Кратчайшие пути для всех пар вершин взвешенного ориентированного графа.
Задача нахождения кратчайших путей из всех вершин формирует таблицу весов, в которой на пересечении строки i и столбца j, находится вес кратчайшего пути из i в j информация о самом пути.
Эту задачу можно решить для орграфа G = (V, E) с заданной весовой функцией w: EàR если |V| раз применить алгоритм поиска кратчайших путей для всех вершин поочередно. Если ребра имеют неотрицательные веса, то можно применить алгоритм Дейкстры. Общее время алгоритма составит O(V(V2+E)) = O(V3) или O(VE log V), если в алгоритме Дейкстры используется очередь с приоритетами. Для разреженных графов это вполне допустимо.
Если в орграфе есть ребра с отрицательным весом, то можно использовать более медленный алгоритм Беллмана - Форда и общее время составит O(V2E) а для плотных графов O(V4).
Изобретены более быстрые алгоритмы. Наиболее удобны эти алгоритмы для орграфов, представленных матрицами. Исходными данными для этих алгоритмов является матрица весов взвешенного орграфа W = (wij) элементы равны:
Веса ребер могут быть отрицательными, но предполагается, что циклов отрицательного веса в орграфе нет.
Алгоритм формирует матрицу D = (dij), элементы которой dij = d(i, j) (вес кратчайшего пути). Кроме того, формируется матрица предшествования P =(pij), в которой pij является вершиной
предшествующей вершине j на одном из кратчайших путей из i j. pij = NIL для i = j или, если пути из i в j нет. Для каждой вершины iÎV можно выделить подграф предшествования Gp, i = (Vp, i, Ep, i), где Vp, i, = {jÎV: pij ¹ NIL} È {i}
Ep, i, = {(pij, j): jÎ Vp, i, и pij ¹ NIL}.
Имея такую матрицу, можно построить путь из вершины i в j:
All_Pathes(P, i, j)
1. if i = j
2. then печать i
3. else if pij = NIL
4. then печать "пути из i в j нет"
5. else All_Pathes(P, i, pi, j )
6. печать j
Алгоритм Флойда – Уоршолла.
Алгоритм Флойда - Уоршолла является алгоритмом динамического программирования. Алгоритм допускает ребра с отрицательным весом, но не допускает циклы с отрицательным весом.
Строение кратчайшего пути.
Введем понятие промежуточной вершины: если есть простой путь p = <v1, v2, ..., vi >, то вершины v2, v3, ... vi-1 называются промежуточными.
Для простоты будем обозначать вершины графа G числами 1, 2,..., n. Рассмотрим подмножество вершин k £ n. Для каждой пары вершин i, j Î V рассмотрим все пути из i, j включающие в путь только вершины {1, 2,...,k}.
Среди них можно выделить путь с минимальным весом. Вес этого пути можно получить, зная вес минимального пути между i, j, включающего вершины {1, 2,...,k-1}.
При добавлении вершины k между вершинами i и j, новый минимальный путь может содержать вершину k в качестве промежуточной или нет.
Если вершина k не вошла в минимальный путь, то новый минимальный путь включает в себя минимальный путь для множества {1, 2,...,k-1}.
Если вершина k промежуточная, то новый минимальный путь разбивается на 2 участка.
Минимальные пути p1 и p2 включают в себя вершины {1, 2, ..., k-1}, которые также должны быть минимальны.
Исходя из этих рассуждений, можно выделить рекуррентное соотношение между решениями подзадач.
Пусть d ij (k) - вес кратчайшего пути из вершины i в j с промежуточными вершинами из подмножества {1, 2,...,k}.
При k = 0прормежуточных путей нет и d ij (0) =wij
В общем случае:
Матрица D(n) = d(n)ij содержит искомое решение, т. е. d(n)ij=d(i, j) для всех i, j Î V, т. к. разрешены любые промежуточные вершины.
Помимо весов кратчайших путей параллельно в матрице p фиксируются p(k)ij
Вычисление кратчайших путей снизу вверх.
Входом алгоритма является матрица весов, результатом - матрица весов кратчайших путей D(n).
Floyd_Warshall (W)
1. n← |V[G]|
2. D(0) ←W
3. for i←1 to n
4. for j←1 to n
5. if (wij¹¥) then pij←i
6. pii←nil
7. else pii←nil
8. for k←1 to n
9. do for i←1 to n
10. do for j←1 to n
11. do if (d(k)ij) ←min (d(k-1)ij, d(k-1)ik + d(k-1)kj)
12. return D(n)
Пусть дан граф:
 |
 |
 |  |
Транзитивное замыкание орграфа.
Задача о транзитивном замыкании состоит в следующем: дан орграф G=(V, E) с вершинами 1, 2, ...,n. Требуется определить для любой пары вершин i, j ÎV существует ли в графе путь из вершины i в вершину j. Транзитивным замыканием орграфа G называется орграф G*=(V, E), где E*={(i, j): в графе G существует путь из i в j}. Транзитивное замыкание можно вычислять за время O(n3) при помощи алгоритма Флойда - Уоршолла считая, что все ребра имеют вес 1. В результате dij<n, если между вершинами i и j существует путь, или dij=¥, если между вершинами i и j пути нет. Для решения задачи используется модифицированный алгоритм Флойда - Улршолла. В нем операции “min” и “+” заменяются на логические операции И (Ù) и ИЛИ (Ú). Положим t(k)ij=1, если в графе G существует путь из i в j с промежуточными вершинами из множества {1, 2,...,k} и t(k)ij=0, если такого пути нет. Ребро (i, j) принадлежит транзитивному замыканию G* тогда и только тогда, когда t(n)ij=1.
Для k ³1: t(k)ij = t(k-1)ij Ú ( t(k-1)ik Ù t(k-1)kj)
Пример:
 |
Алгоритм транзитивного замыкания последовательно вычисляет матрицы T(k) =(t(k)ij) для k = 1,2,...,n.
Transitive_Closure(G)
1. n←V[G]|
2. for i←1 to n
3. do for i←1 to n
4. do if i=j или (i, j)ÎE[G]
5. then t(0)ij ←1
6. else =t(0)ij←0
7. for k←1 to n
8. do for i←1 to n
9. do for j←1 to n
10. do t(k)ij ← t(k-1)ij Ú ( t(k-1)ik Ù t(k-1)kj)
11. return T(n)
Алгоритм Джонсона нахождения всех пар кратчайших путей.
Этот алгоритм работает эффективнее, чем алгоритм Флойда - Уоршолла для разреженных графов. Его время O(V2 log V + VE). Алгоритм либо формирует матрицу кратчайших путей, либо сообщает, что в графе имеется цикл отрицательного веса. Работа алгоритма основана на использовании алгоритмов Беллмана - Форда и Дейкстры.
Особенностью алгоритма является изменения весов ребер графа, т. о. чтобы они были неотрицательны, и можно было бы применить алгоритм Дейкстры к каждой вершине.
При изменении весов ребер должны быть соблюдены следующие условия:
1) Кратчайшие пути в графе не изменяются, т. е. для любой пары вершин u, v ÏV кратчайший путь с точки зрения исходной весовой функции w совпадает с кратчайшим путем с точки зрения новой весовой функции ~w.
2) Все новые веса ~w(u, v) неотрицательны.
Необходимо подобрать способ изменения весов ребер с соблюдением этих условий.
Пусть дан граф G=(V, E) с весовой функцией w: EàR. Введем весовую функцию для вершин графа h: VàR.
Рассмотрим новую весовую функцию ~w: EàR, такую, что ~w(u, v)= w(u, v) + h(u) - h(v). Тогда любой кратчайший путь p = (v0, v1,..., vk) относительно w будет совпадать с кратчайшим путем относительно ~w.
Вес любого пути v0 vk относительно ~w(p) равен:
~w(p)= w(p) + h(v0) - h(vk).
Т. е. для всех путей с фиксированным началом и концом разница между старым и новым весом постоянна и поэтому кратчайшие пути для новой и старой весовой функции совпадают.
~w(p)= w(v0, v1,) + h(v0) - h(v1) + w(v1, v2,) + h(v1) - h(v2) +... +w(vk-1, vk,) + h(vk-1) - h(vk) =
= w(v0, vk,) + h(v0) - h(vk)
Второе следствие при таком преобразовании:
Если граф G содержит отрицательный цикл относительно весовой функции w, то он содержит этот же отрицательный цикл относительно функции ~w. Это следствие исходит из того, что вес цикла равен:
~w(p)= w(p) + h(v0) - h(v0).
Чтобы перейти к новой весовой функции с неотрицательными весами нужно подобрать весовую функцию h: VàR.
 |
Для орграфа G=(V, E) построим эквивалентный орграф G`=(V`, E`) с дополнительной вершиной S, которая имеет только исходящие дуги нулевого веса ко всем остальным вершинам.
Введение этой вершины не изменит путей в новом графе, поскольку вершина S, не может быть вставлена в качестве промежуточной в пути, т. к. не имеет входящих ребер. Она может быть только начальной вершиной пути. Новый граф содержит цикл отрицательного веса, если таковой содержится в исходном графе.
Пусть граф G`, как и граф G не содержит цикла отрицательного веса. Пусть вес каждой вершины равен весу кратчайшего пути до этой вершины S, т. е. h(v) = d(S, v) для " vÎV`.
Для вершин, лежащих на кратчайшем пути выполняется свойство: h(v)£h(u)+w(u, v). Поэтому w(u, v) + h(u) - h(v) ³ 0, т. е. новая весовая функция ~w(u, v) = w(u, v) + h(u) - h(v) неотрицательна.
Далее для прокладки кратчайших путей используется алгоритм Дейкстры.
 |
Орграф для алгоритма Джонсона лучше представит в виде списков смежности. Это представление больше подходит для разреженных графов.
Алгоритм возвращает матрицу D = |dij| размера |V| * |V|, где dij = d(i, j), или возвращает сообщение о том, что граф имеет отрицательный цикл. Вершины нумеруются от 1 до |V|.
Johnson(G)
1. Создать граф G`, для которого V[G`] = V[G]È{S} и E[G`] = E[G]È{S, v}: vÎV[G]
2. if Bellman_Ford(G`, w, S) = FALSE
3. then печать "имеется цикл отрицательного веса"
4. else for (для) каждой вершины vÎV[G`]
5. do h(v)ßd[v] d[v] вычислено в Bellman_Ford
6. for (для) каждого ребра (u, v)ÎE[G`]
7. 
do ~w(u, v)ßw(u, v) + h(u) - h(v)
8. for (для) каждой вершины uÎV[G]
9. do Dijkstra(G, ~w, u) вычисление |~d|
10. for (для) каждой вершины vÎV[G]
11. do d ß ~d[v] + h[v] - h[u] вычисление |d|
12. return D
Общее время работы алгоритма - O(VE log V), что меньше, чем в алгоритме Флойда - Уоршолла (O(V3)).
Паросочетания в двудольном графе.
Двудольным графом называется граф, в котором все вершины разбиты на два подмножества V1 и V2 так, что каждое ребро графа имеет один конец в V1, а другой в V2.
Задача поиска паросочетания в двудольном графе заключается в следующем: Необходимо найти такое подмножество ребер, в котором нет инцидентных ребер, т. е. ребер имеющих концом одну и ту же вершину.
Задача нахождения максимального паросочетания заключается в поиске максимального подмножества инцидентных ребер.
Полным паросочетанием называется подмножество неинцидентных ребер, соединяющих все вершины графа. Полное паросочетание является максимальным паросочетанием.
Примером задачи поиска максимального паросочетания является следующая задача:
Пусть в графе заданы группа вершин, соответствующих читаемым курсам, и группа вершин, соответствующая преподавателям способным читать те или иные курсы. Преподавтель может читать более одного курса.
 |
Требуется найти такое распределение курсов, чтобы на курс пришлось не более одного преподавателя. Кроме того требуется задействовать максимальное количество преподавателей. Другая задача - задача свахи. Имеется n - женихов n - невест. У женихов и невест есть от одного до нескольких предпочитаемых кандидатур. Задача свахи устроить максимальное количество свадеб, чтобы у каждого жениха и невест была кандидатура.
Существуют прямые способы простого перебора всех возможных паросочетаний и выбора из них максимального по числу ребер. Но время такого подхода экспоненциально зависит от числа вершин. Метод, который дает эффективное решение используют чередующуюся цепь.
Пусть M - паросочетания в графе G. Относительно паросочетания М вершины графа делятся на два подмножества - парные вершины {Vп} и непарные (свободные) вершины {Vнп}. Паросочетание М можно увеличить, если построить путь Р, соединяющий 2 непарные вершины и включающий в одно или несколько ребер паросочетания. Особенностью этого пути является то, что в нем чередуются ребра, не принадлежащие паросочетанию, и принадлежащему на концах пути находятся ребра ÏМ.
Имея чередующуюся цепь можно увеличит паросочетание М, удалив из него те ребра, которые входят в цепь Р, и добавить вместо них ребра, которые не входили в паросочетание. Эту операцию называют симметрической разностью множеств МDР, в которую входят в те элементы двух множеств, которые принадлежат или М или Р.
Пример: М = {1 - 6, 3 - 7, 4 - 8}
Vп = {1, 3, 4, 6, 7, 8}
 |
Vнп = {2, 5, 9, 10}
 |
Чередующаяся цепь: P = {2 - 6, 6 - 1, 1 - 8, 8 - 4, 4 - 9}
Симметрическая разность, МDР = {2 - 6, 1 - 8, 4 - 9, 3 - 7}. Эта разность является новым увеличенным паросочетанием.
Паросочетание будет максимальным, тогда когда не существует чередующейся цепи относительно М.
Алгоритм нахождения максимального паросочетания следующий:
Max_Pair(G)
1. Mß0
2. repeat
3. PßPath_Link(G, M)
4. MßMDP
5. until P ¹ 0
Алгоритм Path_Link формирует чередующуюся цепь в виде множества ребер.
Алгоритм делит множество вершин на парные и непарные относительно паросочетания {Vp} и {Vnp}.
Построение чередующейся цепи напоминает алгоритм обхода в ширину и выполняется по шагам i = 0, 1, 2, ... . На нулевом шаге вершины графа делятся на подмножества {Vp} и {Vnp} и выбирается произвольно непарная вершина. Далее на 1 - м шаге выбирается ребро, не принадлежащее паросочетанию М и ведущее к парной вершине из множества {Vп}.
На 2 - м шаге и последующих четных шагах выбирается инцидентная для последней вершины пути ребро, принадлежащее М.
На 3 - м и последующих шагах выбирается инцидентное последней вершине пути ребро, не принадлежащее М. При этом, в первую очередь выбирается ребро, ведущее к свободной вершине. Если таковой нет, то выбирается ребро, не принадлежащее М и ведущие к парной вершине.
Вершины, включенные в путь Р удаляются из множества {Vнп}.
Процесс построения заканчивается, когда будет включено ребро, ведущее к непарной вершине.
Path_Link(G, M)
1. Vpß{vÎM}
2. VnpßV[G]\Vp
3. Pß 0
4. Выбор v0ÎVnp
5. Выбор (v0, v1) D v1 ÎVp
6. PßPÈ( v0, v1)
7. K = 0
8. Repeat
9. KßK + 1
10. Vnp = Vnp\vk
11. Выбор (vk, vk+1) ÎM
12. PßPÈ( vk, vk+1)
13. KßK + 1
14. if $ ( vk, vk+1) Ï M and vk+1ÏVp
15. then PßPÈ{( vk, vk+1) Ï M}
16. else p ßPÈ{( vk, vk+1) Ï M }
17. until vk+1 Î Vp
18. return P
