Г(0)

Г(з)

Г(2)

Рис. 26.4 26.5 Ориентированный граф и матрицы , вычисленные алгоритмом построения транзитивного замыкания.

арифметические операции с целыми числами, поэтому процедура Transitive-Clusure эффективнее алгоритма Флойда-Уоршолла. Кроме того, использование булевских переменных вместо целых сокращает объём используемой памяти.

В разделе 26.4 мы увидим, что аналогия между алгоритмами Флойда-Уоршолла и построением транзитивного замыкания не случайна: оба алгоритма основаны на алгебраической структуре, называемой «замкнутое полукольцо».

Упражнения

26.2-1 Исполните алгоритм Флойда-Уоршолла для взвешенного ориентированного графа рис. 26.2, найдя все матрицы DkK

26.2-2 В приведённом нами виде алгоритм Флойда-Уоршолла требует в (га3) памяти для хранения матриц L>(fc) = (d\f). Конечно, можно сэкономить место, если хранить только две соседние матрицы. Оказывается, можно пойти ещё дальше: доказите, что если в процедуре Floyd-Warshall убрать верхние индексы, то она по-прежнему будет вычислять веса кратчайших путей.

{\sc Floyd-Warshall}$(W)$\\

\verb11 I$n \leftarrow rows[W]$\\

\verb2 $D \leftarrow W$\\

\verb3 I for $k \leftarrow 1$ to $n$\\

\verb4I do for $i \leftarrow 1$ to $n$\\

\verb5I do for $j \leftarrow 1$ to $n$\\

\verb6l$d {ij} \leftarrow \min(d {ij},

d {ik>+d {kj»$\\

\verb7 I return $D$

Тем самым мы сократили объём требуемой памяти до ©(га2).

26.2-3 Добавьте в процедуру Floyd-Warshall вычисление матриц предшествования по формулам (26.6) и (26.7). Докажите, что для любой вершины г £ V подграф предшествования GVti является деревом кратчайших путей из вершины г.

26.2-4 Будет ли правильно вычислена матрица предшествования

П, если изменить формулу (26.7) так:

kj

если

если

26.2-5 Как можно использовать результат работы алгоритм Флойда-Уоршолла, чтобы узнать, есть ли в графе цикл отрицательного веса?

26.2-6 Еще один способ построения кратчайших путей в алгоритме Флойда-Уоршолла таков. Пусть ipf (г, j, /г = 1,2,... , га) есть промежуточная вершина с максимальным номером на кратчайшем пути из г в j с промежуточными вершинами из множества {1, 2,... , к}. Напишите рекурентное соотношение для ipf и допо-

(к)

ните процедуру Floyd-Warshall вычислением значении tp-.

Наконец, измените функцию Print-All-Pairs-ShortestPaths так, чтобы входом для неё служила матрица Ф = (<р). Объясните аналогию между матрицей Ф и таблицей s в задачи об оптимальной расстановке скобок в произведении матриц (раздел 16.1).

26.2-7 Придумайте алгоритм вычисления транзитивного замыкания ориентированного графа G = (V, Е) с временем работы

26.2-8 Предположим, что транзитивное замыкание ориентированного ациклического графа может быть построено за время f(V,E), где f(V,E) = Q(V + Е) и / - монотонно возрастающая функция. Покажите, что тогда транзитивное замыкание произвольного ориентированного графа может быть построено за время

Алгоритм Джонсона для разреженных графов

Алгоритм Джонсона находит кратчайшие пути для всех пар вершин за время 0(V2lgV + VE), и поэтому для достаточно разреженных графов эффективнее повторного возведения в квадрат матрицы смежности графа и алгоритма Флойда-Уоршолла.

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

Алгоритм Джонсона основан на идее изменения весов (reweight-ing). Если веса всех рёбер графа неотрицательны, то можно найти кратчайшие пути между всеми парами вершин, применив алгоритм Дейкстры к каждой вершине. Используя фибоначчиевы кучи, мы можем сделать это за время 0(V2 lg V-\-VE). Если же в графе имеются ребра с отрицательным весом, то можно попытаться свести задачу к случаю неотрицательных весов, изменив весовую функцию. При этом должны выполняться такие свойства:

1. Кратчайшие пути не изменились: для любой пары вершин и, v £

0(VE).

0(f(V,E)).

V, кратчайший путь из и в v с точки зрения весовой функцией w является также кратчайшим путём с точки зрения w и наоборот.

2. Все новые веса w(u,v) неотрицательны.

Как мы увидим, новая весовая функция w с такими свойствами может быть построена за время 0(VE). Кратчайшие пути сохраняются

Следующая лемма указывает простой общий способ изменить весовую функцию, не меняя кратчайших путей. В её формулировке длины кратчайших путей с весовыми функциями w и w обозначаются через 8 и 8 соответственно.

Лемма 26.1 (Изменение весов не меняет кратчайших путей) Пусть G = (V, Е) - взвешенный ориентированный граф с весовой функцией w : Е -> Ж. Пусть h : V -> М. - произвольная функция с вещественными значениями, определённая на вершинах графа. Рассмотрим новую весовую функцию

Тогда (а) произвольный путь р = (vo,vi,... ,vk) является кратчайшим относительно w тогда и только тогда, когда он будетт кратчайшим относительно w; (Ь) граф G содержит цикл с отрицательным w-весом тогда и только тогда, когда он содержит цикл с отрицательным w-весом.

Доказательство. Оба утверждения леммы следуют из равенства

В самом деле, из него следует, что для путей с фиксированными началом и концом разница между старым и новым весом постоянна (тем самым один и тот же путь будет кратчайшим). Кроме того, видно, что для циклов суммарный вес в старом и новом смысле одинаков, так как разница h(vo) - h(vk) обращается в 0.

Равенство (26.10) проверить легко. Для каждого ребра пути имеем

Если мы теперь сложим эти равенства для всех рёбер, то промежуточные члены сократятся, и получится равенство (26.10). Как получить неотрицательные веса?

Теперь надо подобрать функцию h так, что бы изменённые веса w(u, v) были неотрицательны. Это можно сделать следующим образом. По данному ориентированному взвешенному графу G = (V, Е) с весовой функцией w построим новый граф G = (V, Е) с одной дополнительной вершиной s (другими словами, V = V U {s}), из которой идут рёбра нулевого веса во все вершины графа V

(26.9)

(26.10)

w(vi, vl+1) = w(vi, vl+1) + h(vi) - h(vi+1).