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

При осуществлении операции (1) сравнивается длина dih дуги A ik и длина цепи N t — Nj — N k, а затем длине дуги A ih присваи­ вается значение йц + djk, если dik > di} + djk.

Оказывается, что если выполнить операцию (1) последователь­ но для каждого узла Nj (j = 1 , 2 , . . ., п), то полученные в ре­

зультате значения d^ будут длинами кратчайших цепей между

А

Р и с . 10.4

всеми парами узлов. (Заметим, что при этом общий объем вычисле­ ний не превышает п (п — 1 ) (п — 2 ) действий сложения и срав­

нения.)

Идея доказательства этого факта заключается в следующем. Каждая кратчайшая цепь должна состоять из базисных дуг исход­ ной сети. Значит, надо доказать, что в результате выполнения алгоритма будет получена базисная дуга, длина которой равна сумме длин базисных дуг, входящих в кратчайшую цепь. Рас­ смотрим произвольную кратчайшую цепь; например, одна такая цепь представлена на рис. 10.4. При выполнении операции (1) в сеть будут последовательно добавляться базисные дуги, изобра­ женные пунктиром на рис. 10.4. Так как сумма расстояний по любому направленному циклу в сети неотрицательна, то понятие кратчайшей цепи между любыми двумя узлами имеет смысл. Если при выполнении операции (1) получится дуга А рд, длина которой больше кратчайшего расстояния между N p и N q, то на некотором дальнейшем шаге длина этой дуги обязательно изменится и станет равной кратчайшему расстоянию между N p и N q х). После этого величина dpq уже не будет изменяться, поскольку она не может*)

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

быть уменьшена. На рис. 10.4 показана произвольная кратчайшая цепь между узлами, скажем, N 2 и N 9, состоящая из базисных дуг А 24, А 46, А в1, A i3 и А 39. Если выполнить операцию (1) последо­

вательно для каждого узла N } (/ = 1, 2, . . ., 9, . . .), то новые базисные дуги будут появляться одна за другой: сначала И63, затем + в9, А 2в и А 29.

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

В самом начале элемент (i, к) таблицы, стоящий на пересечении i-й строки и к-то столбца, полагаем равным к. После выполнения операции (1 ) пусть элемент (t, к) ука­

зывает первый промежуточный узел в кратчайшей цепи между N t vi N k, если такой узел существует. Если такого промежуточного узла не существует, то полагаем элемент (i , к) равным к.

Во всех вычислениях мы до сих пор полагали, что dit = 0 для всех i. Если положить dn = оо для всех г, а в опе­ рации (1 ) разрешить, чтобы i = к, то

последовательное выполнение опера­ ции (1 ) дает возможность найти кратчайшие циклы, содержащие

узел N f Если при таких вычислениях величина du становится отрицательной, то это показывает, что в сети существует отрица­ тельный цикл (т. е. такой, у которого сумма длин входящих дуг отрицательна). Задача нахождения отрицательных циклов в сети имеет много различных приложений.

Рассмотрим сеть, изображенную на рис. 10.5; длины дуг ука­ заны в табл. 10.1. Необходимо найти кратчайшие цепи между всеми парами узлов.

Выполнение операции (1) при / = 1 заключается в том, что пересчитываются все элементы табл. 1 0 .1 , не лежащие в первой

строке или первом столбце. Имеем

d23: = min (d23, d2i + ^i3) = nim(oo, И + 30) = 41, d32 : = min (d32, d3i + dl2) = min (oo, 3 0 + 11) = 41;

все остальные элементы не изменяются.

Выполнение операции (1) при j = 2 заключается в том, что пересчитываются все элементы табл. 1 0 .1 , не лежащие во второй

строке и втором столбце. Заметим, что при этом уже используются результаты вычислений при j — 1. Имеем

остальные элементы не изменяются.

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

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

Пусть, например, нужно найти кратчайшую цепь из N t в N e. Тогда по табл. 10.3 сначала находим элемент (1 ,6 ) = 2 . Затем

в N q, то по справочной таблице сначала находим элемент (р , q) = = к, который означает, что узел N h является первым промежуточ­ ным узлом в кратчайшей цепи из N p в N q. Затем находим элемент (к, q), который указывает первый промежуточный узел в кратчай­ шей цепи из N k в N q. Этот процесс продолжается до тех пор, пока не будет найден элемент (i, q) = q, который означает, что найдены

202 гл. 10. КРАТЧАЙШИЕ ЦЕПИ И ПОТОКИ МИНИМАЛЬНОЙ с т о и м о с т и

Таблица 10.2