41197

Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)

Лекция

Физика

Именно {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to n do {3} if i = j then else ; {4} for k := 1 to n do {5} for i := 1 to n do {6} for j := 1 to n do {7} ; {есть матрица смежности транзитивного замыкания т. {Инициализация: } {1} for i := 1 to n do {2} for j := 1 to n do {3} if i = j then else ; {4} for k := 1 to n do {5} for i := 1 to n do {6} if then ; {есть матрица смежности транзитивного замыкания т. Следовательно матрицу можно вычислить с помощью алгоритма:...

Русский

2013-10-23

280.5 KB

71 чел.

Лекция 11 часть 2 (весна 2009 года)

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

Часть 1. Вспомогательная тема:

Транзитивное замыкание графа. Алгоритм Уоршалла (Warshall)

 Задан ориентированный граф G = (V, E). Как и ранее n = |V|, m = |E|.

 Транзитивным замыканием графа G называется граф G*, состоящий из тех же вершин, т.е. G* = (V, E*), множество рёбер которого есть

E* = {(u, v): ( V) & ( V) & (существует путь из u в v в графе G) }.

Иными словами, в графе транзитивного замыкания G* дуга из вершины u в вершину v имеется только тогда, когда в исходном графе G есть путь из u в v.

Например, для графа G, изображенного на рис. 1.а, его транзитивное замыкание дано на рис. 1.б.

Матрица смежности A графа G, изображенного на рис. 1.а, есть

A = ,

а матрица смежности А* транзитивного замыкания G* этого графа есть

А* = .

Можно ввести понятие матрицы путей (или матрицы достижимости) P графа G, так, что pij = 1, если существует путь из вершины  в вершину  в графе G, и pij = 0 в противном случае. Очевидно, что матрица путей P графа G совпадает с матрицей смежности А* его транзитивного замыкания G*.

Далее важную роль в нашем рассмотрении будут играть степени матрицы смежности.

 Утверждение. Пусть A есть матрица смежности графа G. Элемент  матрицы  равен числу путей длины k из вершины  в вершину  (V, V).

 Доказательство проведем по индукции:

А) при k = 1 утверждение очевидно (по определению матрицы смежности);

Б) пусть утверждение верно для k = l,  покажем, что оно верно и для k = l + 1; действительно  и

.

Рассмотрим отдельное слагаемое этой суммы, соответствующее вершине . Если , то это слагаемое не дает вклада в сумму. Если же  и , то {число путей длины l + 1 из вершины  в вершину }, причём из l шагов состоит каждый из путей из вершины  в вершину  и один шаг ведет из вершины в вершину. Рисунок

наглядно изображает это рассуждение (пунктиром показаны пути, а дуга – сплошной линией). Таким образом, вся сумма даст число путей длины l + 1 из вершины  в вершину .

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

Очевидно, что элементы матрицы

дают число путей длины не более чем 4 между каждыми двумя вершинами. Очевидно также, что если в этой матрице заменить все ненулевые элементы на 1, то мы получим матрицу путей P графа G или, что то же, матрицу смежности A* его транзитивного замыкания G*.

 В общем случае пусть  и определим матрицу P как

Очевидно, что это и есть матрица путей P графа G или, что то же, матрица смежности A* его транзитивного замыкания G*. Т.к. перемножение двух матриц осуществляется за время O(n3), то вычислить матрицу P можно за O(nn3) = O(n4) операций. Заметим, что если нас интересуют циклы по всем вершинам графа, то следует рассмотреть .


Таблица  

 = 

    Пути длины 1

  =  = 

      Пути длины 2

  = 

               Пути длины 3

  = 

               Пути длины 4


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

Определим операции сложения и умножения «булевских» матриц:

C = AB  ,

C = A+B  .

Легко видеть, что эти операции получаются из «обычных» формул для вычисления элементов матриц заменой операций сложения (знак +) на дизъюнкцию или булевское сложение (знак ) и умножения – на конъюнкцию или булевское умножение (знак &).

Нетрудно проверить, что с переопределенными операциями имеем

.

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

Теперь, поскольку нам нужна лишь окончательная степень , то можно воспользоваться бинарным способом вычисления степени, и это приводит к алгоритму сложности O(n3log n), а не O(n4), как ранее.

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

Наше предыдущее рассмотрение фактически основывалось на таком анализе  структуры путей, при котором выделялась последняя дуга и предшествующие ей части пути (см. рисунок на с. 2). Применим другой подход. Пусть вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества. Определим булевские величины  так, что равно 1 или 0 в зависимости от того, существует или нет путь из вершины  в вершину , проходящий через промежуточные вершины только из множества вершин с номерами от 1 до k. Постараемся определить, как связаны элементы  матрицы  с элементами матрицы . Рассмотрим следующий схематичный рисунок.

Рассмотрим соотношение

.

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

Алгоритм Уоршалла состоит в вычислении последовательности матриц . Именно,

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

{есть матрица смежности транзитивного замыкания, т.е. }

Удобно преобразовать этот алгоритм к несколько иному виду. «Свернём» цикл по j в строке 6, переписав строку 7 в виде

{6*}  .

Здесь  обозначают i-ую строку матрицы , i-ую строку матрицы  и k-ую строку матрицы  соответственно, а операции присваивания и дизъюнкции применяются к строкам матриц. При этом цикл в явной форме исчез. Он «спрятан» в операциях со строками матриц. В такой форме удобнее анализировать изменения матриц  при работе алгоритма.

Далее заметим, что теперь строки 6 и 7 в алгоритме можно заменить на следующее

{6*}   if   then  else .

В такой форме отчётливо видно, что при заданном k каждая i-ая строка либо не изменяется (при ), либо при  заменяется на результат побитной дизъюнкции i-ой и k-й строк. Для наглядности изобразим это графически на следующем рисунке (при i < k).

Поскольку при модификации i-ой строки используются только i-ая и k-ая строки, то новое значение  можно было бы записать на место старого  (при i < k или при i > k). При i = k имеем  и, следовательно, k-ая строка при этом не изменяется. Т.о. все преобразования можно производить в матрице B (двумерном булевском массиве) что называется «на месте».

 С учётом этих соображений алгоритм Уоршалла можно записать в следующем окончательном виде.

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   if   then ;

{есть матрица смежности транзитивного замыкания, т.е. }

Очевидно, что сложность этого алгоритма (с учётом неявного цикла внутри строк) есть O(n3), а в случае, когда строка матрицы может быть представлена одной (или несколькими) битовой строкой и операция дизъюнкции строк выполняется за фиксированное время, тогда сложность алгоритма уменьшается до O(n2).

Часть 2. Основная тема:

Алгоритм построения кратчайших путей между всеми парами вершин

Пусть для ориентированного графа G = (V, E) задана матрица стоимостей W(nn).

 Рассмотрим величину  – стоимость кратчайшего пути из вершины  в вершину  среди всех путей, содержащих не более k дуг. Набор этих величин (матрица)  уже использовался нами ранее при анализе (доказательстве корректности) алгоритма Форда-Беллмана (было использовано другое обозначение d[k| j], при этом первая вершина  была фиксирована). Тогда же было использовано рекуррентное соотношение

.

Докажите это соотношение, используя вспомогательный рисунок:

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

C = AB  ,

заменив в обычной операции перемножения матриц сложение (знак +) на взятие минимума min, а умножение  (знак ) – на сложение (знак +). Кроме того, определим диагональные элементы весовой матрицы W как . Определим также матрицу как

Тогда получим

для .

Матрица  является результатом решения задачи о кратчайших путях. Вычислить её можно за O(n4) или же, как и в случае транзитивного замыкания, за O(n3log n) операций.

Далее совершенно аналогично случаю транзитивного замыкания рассмотрим более эффективный алгоритм, известный как алгоритм Флойда-Уоршалла.

Пусть, как и ранее в алгоритме Уоршалла, вершины графа пронумерованы числами от 1 до n. Нас будут интересовать пути, проходящие через промежуточные вершины из некоторого определенного множества. Рассмотрим величину  – стоимость кратчайшего пути из вершины  в вершину  среди всех путей, проходящих через промежуточные вершины только из множества вершин с номерами от 1 до k.

Используя тот же схематичный рисунок,

легко доказать справедливость соотношения

.

Следовательно, матрицу  можно вычислить с помощью алгоритма:

{Инициализация: }

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

Самостоятельно докажите, что как и в алгоритме Уоршалла, верхние индексы у матриц  можно убрать, т.е. необходимо иметь в алгоритме только один экземпляр матрицы D и все вычисления с ней проводить «на месте». Т.о. алгоритм Флойда-Уоршалла принимает следующий вид:

{1} for := 1 to n do

{2} for := 1 to n do

{3}  if j then  else ;

{4} for := 1 to n do

{5}  for := 1 to n do

{6}   for := 1 to n do

{7}    ;

Очевидно, что сложность этого алгоритма есть O(n3). Сравнение с алгоритмом Форда-Беллмана обнаруживает любопытный факт: найти кратчайшие пути между всеми парами вершин асимптотически не более трудно, чем кратчайшие пути только от одной вершины до всех остальных!

PAGE 1


 

А также другие работы, которые могут Вас заинтересовать

35994. Мексиканская монументальная живопись XX века. Общая характеристика, основные мастера 43.5 KB
  Ороско 1882 1949 Д. По стилю тематике образам росписей Ороско Риверы Сикейроса можно проследить как менялось отношение художников к действительности: от почти безоговорочной веры в возможность перестройки мексиканского общества в первых фресках до разочарования и горечи от несбывшихся надежд в их работах более позднего времени. У каждого из мастеров разочарование выразилось посвоему: Ороско пришел к болезненной экспрессии Ривера к намеренной стилизации Сикейрос к повышенной динамике усложнению композиции запутанности...
35999. Экономические системы, критерии классификации экономических систем 42.5 KB
  В результате приватизации значительная часть гос. Главными целями приватизации в 1992 г. были: Формирование слоя частных собственников содействующих созданию социальноориентированной рыночной экономики; Повышение эффективности деятельности предприятий; Социальная защита населения и развитие объектов социальной инфраструктуры за счет средств поступивших от приватизации; Содействие процессу стабилизации финансового положения в РФ; Создание конкурентной среды и содействие демонополизации народного хозяйства; Привлечение иностранных инвестиций....
36001. Международные и национальные профессиональные объединения PR-специалистов 42.5 KB
  Международные и национальные профессиональные объединения PRспециалистов 1 М н ассоциация паблик рилейшнз – ИПРА IPR. Кодекс проф поведения ИПРА Венецианский кодекс – принят в мае 1961 в Венеции на Ген ассамблее ИПРА: включает себя параграфы о: личной и проф честности предоставление правдивой информации отношениях со СМИ и общественностью; стучать на нарушителей этики коллегами мае 1965 Афинский кодекс – принят в в Афинах на Ген ассамблее ИПРА изменен в апреле 1968; в 1965 также...