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

83 чел.

Лекция 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


 

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

39760. Определение внимания 129.5 KB
  Различие в восприятии нами внешних воздействий зависит от внимания. Физологические основы внимания. В исследовании физиологических основ внимания особенно большая заслуга принадлежит отечественным физиологам: И.
39761. Понятие воли 131 KB
  Само же понятие воли как стороны сознания формировалось медленно. Сложность изучения проблемы воли состоит в том что как в обыденном так и в научном сознании воля понимается поразному. Пушкина: волю первую твою я исполню как мою или в обыденном языке делать чтото насильно означает делать против своей воли как проявление силы характера противопоставление: волевой безвольный.
39762. Воображение 149.5 KB
  Сходства и различия воображения с восприятием памятью и мышлением; 3 Функции воображения. Физиологические и психологические механизмы воображения воображение и органические процессы 1. Связь воображения с реальностью: а закон двойного выражения чувств б закон общего эмоционального знака в закон эмоциональной реальности 4. Психологический механизм воображения а диссоциация б ассоциация.
39763. ВОСПРИЯТИЕ 73.5 KB
  Физиологической основой восприятия являются процессы проходящие в органах чувств нервных волокнах и центральной нервной системе. Следовательно ощущения могут быть рассмотрены как структурный элемент процесса восприятия. Собственные физиологические механизмы восприятия включаются в процессе формирования целостного образа на последующих этапах когда возбуждение от проекционных зон передается в интегративные зоны коры головного мозга где и происходит завершение формирования образов явлений реального мира. Поэтому интегративные зоны коры...
39764. Деятельностный подход в психологии (С.Л. Рубинштейн, А.Н. Леонтьев) 104.5 KB
  Рубинштейн в качестве компонента в структуре деятельности рассматривал также движения. Движения это механизмы посредством которых осуществляются действия выражающие поведение. Специфические человеческие движения вырабатывались в процессе труда. Движения человека направлены на предмет на орудие как средство труда.
39765. Индивидуальный стиль деятельности 33 KB
  Предпочитаемые человеком операции характеризуют его индивидуальный стиль деятельности. Индивидуальный стиль деятельности создает новые связи между свойствами субъекта. Сочетание объективных и субъективных условий однозначно детерминирует лишь общее направление деятельности и некоторые наиболее общие характеристики операций и движений.
39766. Качества ума 31 KB
  Калмыкова для обозначения общих умственных способностей учащихся использует термин обучаемость под которым понимает сложную динамическую систему интеллектуальных свойств личности формирующихся качеств ума от которых зависит продуктивность учебной деятельности при наличии исходного уровня знаний положительной мотивации и т. Формируясь и развиваясь в процессе онтогенеза качества ума человека как достаточно устойчивые особенности его личности Являются новообразованиями психики которые проявляются в меняющихся условиях мыслительной...
39767. СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ 985.5 KB
  Передача PnP IRP пакетов нижним драйверным слоям. Работа с IRP пакетами. Вспомогательная функция CompleteIrp реализует действия по завершению обработки IRP пакета с кодом завершения status. Процедура ReadWrite_IRPhandler предназначена для обработки запросов Диспетчера ввода вывода которые он формирует в виде IRP пакетов с кодами IRP_MJ_READ IRP_MJ_WRITE по результатам обращения к драйверу из пользовательских приложений с вызовами read write или из кода режима ядра с вызовами ZwReadFile или ZwWriteFile.
39768. СИСТЕМНОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЭИС 1.24 MB
  Требования высокой эффективности СП вызывают необходимость использования специальных языков, к которым принадлежат машинно-ориентированные языки типа Ассемблера, и языки высокого уровня с развитыми формами представления внутренней, прежде всего, адресной информации СП, например, Си или PL/M