Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

194 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ

Подсчитаем, какое число операций сложения и сравнения тре­ буется для выполнения алгоритма. На шаге 3 нужно выполнить не более п операций сложения и п операций сравнения, чтобы получить временные пометки. На шаге 1 нужно выполнить еще не более п сравнений, чтобы получить постоянную пометку. Таким

образом, требуется самое большее 3п операций, чтобы найти одну постоянную пометку. Так как в сети имеется п узлов, то для нахождения кратчайшей цепи потребуется самое большее 3/г2 опе­

раций.

Рассмотрим сеть, изображенную на рис. 10.1, где числа рядом с дугами выражают расстояния. Линии без стрелок обозначают неориентированные дуги; считаем, что у неориентированных дуг

196 ГЛ . 10. КРАТЧАЙШ ИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ

то для решения задачи можно использовать описанный выше алгоритм.

В частности, если gц — di} и ищется кратчайшая цепь в сети, то

найти цепь, через которую можно пропустить наибольший поток

Условие (26) здесь выполняется. Для того чтобы применить опи­ санный выше алгоритм, следует в качестве временной пометки L'sk принять величину макси­ мального потока, который можно пропустить из N s в N k\ выражение (1 ) следует заме­

нить на следующее:

L ’sk' —max[Lsft, min(Lsr, brk)].

В качестве постоянной по­ метки Lsh следует взять мак­ симальную из временных пометок L'sh.

Аналогичные изменения в алгоритме следует проводить при решении других задач,

удовлетворяющих условиям (2). Следует отметить, что утвержде­ ние (2 ) является достаточным (но не необходимым) условием при­

менимости описанного выше алгоритма.

В заключение параграфа рассмотрим одно интересное и не совсем очевидное приложение задачи о кратчайшей цепи, а именно задачу нахождения минимального разреза в (s, ^-плоской сети [64].

Сеть называется плоской, если ее можно начертить на плоско­ сти так, чтобы все ее дуги пересекались только в узлах сети. Неориентированная плоская сеть называется (s, 1)-плоской, если после добавления к ней дуги A st она останется плоской. Напри­ мер, плоская сеть, изображенная на рис. 1 0 .2 , не является (s, t)-

плоской. Эта же сеть, но без дуги А 23, уже будет (s, ^-плоской. Рассмотрим (s, г)-плоскую сеть, которая получится, если из сети на рис. 10.2 удалить дугу А 23. Пусть числа рядом с дугами

выражают их пропускные способности. Требуется найти мини­ мальный разрез, отделяющий узлы N s и N t.

Эта задача, конечно, может быть решена посредством нахож­ дения максимального потока с помощью метода расстановки поме­ ток. Но оказывается, ее можно решить проще: минимальный раз­ рез в исходной сети соответствует кратчайшей цепи в сети, двой­ ственной к ней х).

Двойственная сеть строится следующим образом. Сначала чер­ тится дуга A st, если Bi исходной сети этой дуги не было. Получится

плоская сеть с п узлами. Плоскость чертежа окажется раз­ деленной на грани (области, ограниченные ребрами и не содержа­ щие внутри себя ни вершин, ни ребер). Дуга A st будет разделять две грани, одна из которых является внешней. Поместим по одно­ му узлу в каждую из этих граней и обозначим их через N's и N t’. Аналогично, поместим по одному узлу в каждую из граней, раз­ деленных дугой A tj, и обозначим их через N\ и N ]. Проведем в двойственной сети дуги Ац, которые связывают узлы N\ и Nj.

*) Задача нахождения максимального потока в (s, г)-плоской сети проще, чем в общем случае, и эффективно решается (за О (п2) действий) без использования двойственной сети (см. [64], стр. 399).

Алгоритм поиска кратчайшей цепи в двойственной сети будет не сложнее (по числу действий) алгоритма нахождения максимального потока в исход­ ной сети, если число узлов в двойственной сети не превышает (по порядку) числа узлов в исходной цепи. Это действительно так: число узлов в двой­ ственной сети равно числу граней / в исходной сети, а в плоской сети / ^ ^ 2п — 4 (см., например, [18*]).— Прим, перев.

198 ГЛ. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ СТОИМОСТИ

Каждой дуге A tj исходной сети будет соответствовать дуга А\} двойственной сети. Каждому разрезу, разделяющему N s и N t в исходной сети, будет соответствовать некоторая цепь из N's в N't. Положим, что пропускная способность btj дуги A tj равна длине dtj дуги A'ij. В этом случае кратчайшая цепь из N's в Nt будет соответствовать минимальному разрезу, разделяющему N s и N t. Рис. 10.3 иллюстрирует описанное построение.

10.2. Многополюсные кратчайшие цепи (Флойд [63], Ху [111], Мерчленд [158], Уоршелл [209J)

В этом параграфе рассматривается задача нахождения крат­ чайших цепей между всеми парами узлов сети. Предполагается, как и в § 1 0 .1 , что длины йц могут не удовлетворять неравенству

треугольника и условию симметричности. В отличие от § 10.1

теперь величины dtj могут быть и отрицательными. При этом делается предположение менее ограничительное, чем условие da ^ 0 : сумма длин дуг по любому направленному циклу должна

быть неотрицательна (иначе понятие кратчайшей цепи теряет смысл). Заметим, что для любой неориентированной дуги A iS последнее предположение не менее ограничительно: из него сле­ дует, что dt] ^ 0 (поскольку неориентированную дугу можно рас­

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

Дуга).

Как отмечалось в § 10.1, задача оказалась бы тривиальной, если бы выполнялось неравенство треугольника dtj + djk ^ dth; в этом случае кратчайшей цепью между произвольной парой узлов 7V, и N j была бы сама дуга Ац. В произвольной сети лишь некото­ рые дуги А и являются кратчайшими цепями из N t в Np, такие дуги будем называть базисными. Заметим, что в § 10.1 все дуги дерева были базисными (обратное неверно).

Предположим, что известна кратчайшая цепь, скажем, из узла N p в узел N q. Тогда эта цепь должна состоять только из базисных дуг, в противном случае она не будет кратчайшей. Если теперь

узлов можно решить, добавив базисные дуги (если таких дуг в сети не было) между всеми парами узлов. При добавлении базисной дуги ей ставится в соответствие длина, равная длине кратчайшей цепи, состоящей из базисных дуг исходной сети.

Рассмотрим следующую операцию, определенную для фикси­