Часть 5. Алгоритмы на графах. этой задачи. Мы завершаем этот раздел анализом двух примеров проявления таких про­блем.

этой задачи. Мы завершаем этот раздел анализом двух примеров проявления таких про­блем.

Прежде всего, мы рассмотрим отношение между транзитивным замыканием и зада­чей определения кратчайших путей для всех пар вершин (all-pairs shortest-paths). Для оргра­фов задача заключается в том, чтобы найти для каждой пары вершин ориентированный путь с минимальным числом ребер.

Для заданного орграфа мы инициализируем целочисленную матрицу А размерности V на V, устанавливая элемент A[s][t] в 1, если в орграфе существует ребро, ведущее из s в t, или, присваивая ему значение сигнальной метки V, если такое ребро не существует. Эту задачу выполняет следующий программный код:

for (i = 0; i < V; i++) for (s = 0; s < V; s++) for (t = 0; t < V; t++)

if (A[s][i] + A[i][t] < A[s][t]) A[s][t] = A[s][i] + A[i][t};

Этот программный код отличается от алгоритма Уоршалла, который мы рассматри­вали непосредственно перед тем, как дать формулировку свойства 19.7, только операто­ром if во внутреннем цикле. В самом деле, в соответствующей абстрактной форме эти вычисления ничем не отличаются (см. упражнения 19.55 и 19.56). Преобразование дока­зательства свойства 19.7 в прямое доказательство того, что этот метод достигает желае­мой цели, достаточно просто. Этот метод является частным случаем алгоритма Флойда (Floid's algorithm) поиска кратчайших путей во взвешенных графах (см. главу 21). Реше­ние для ориентированных графов, построенное на использовании поиска в ширину, ко­торое мы рассматривали в разделе 18.7, также способно отыскивать кратчайшие пути в орграфах (модифицированных соответствующим образом). Кратчайшие пути подробно рассматриваются в главе 21, поэтому мы отложим детальное сравнение рабочих характе­ристик обоих алгоритмов до этой главы.

Во-вторых, как мы уже могли убедиться, задача транзитивного замыкания также тес­но связана и с задачей перемножения булевых матриц. Базовые алгоритмы решения обоих задач, которые мы рассматривали выше, требуют для своего выполнения с использова­нием аналогичной схемы вычислений время, пропорциональное V³. Известно, что умно­жение булевых матриц является сложной вычислительной задачей: известны алгоритмы, обладающие большим быстродействием, чем простые методы, однако вопрос о том, до­статочны ли выгоды, получаемые от их использования, чтобы оправдать усилия, затрачи­ваемые на их реализацию, остается открытым. Этот факт имеет большое значение в дан­ном контексте, поскольку мы можем воспользоваться быстрым алгоритмом умножения булевых матриц для разработки быстрого алгоритма транзитивного замыкания (он мед­леннее алгоритма умножения всего лишь в lgV paз), применяя для этой цели метод мно­гократного возведения в квадрат, представленный на рис. 19.15. И наоборот, мы можем понизить уровень сложности вычисления транзитивного замыкания.

Свойство 19.9. Мы можем использовать алгоритм транзитивного замыкания для вычис­ления произведения двух булевых матриц, при этом различие во времени исполнения не пре­вышает некоторого постоянного коэффициента.