Cтраница 1
Процедура расстановки пометок в [ алгоритме, описанном в разд. [1]
Процедура расстановки пометок в алгоритме, описанном в разд. [2]
Процедура расстановки пометок осуществляется следующим образом. [3]
Процедура расстановки пометок предназначена для выделения путей ( цепей) от источника к стоку, по которым можно увеличивать поток. Процедура изменения потока заключается в осуществлении этого увеличения. Добавим, что процедурой расстановки пометок устанавливаются также существование начального допустимого потока и оптимальность потока. Если сток помечен не до конца и больше пометки расставлять невозможно, то это признак того, что или допустимого потока нет, или после последнего изменения получен оптимальный поток. [4]
Продолжаем процедуру расстановки пометок до тех пор, пока либо не будет помечен сток, либо не останется непомеченных вершин. [5]
Рассмотрим процедуру расстановки пометок, которая по данному дереву Т строит нужный цикл. [6]
Общий шаг А2 процедуры расстановки пометок продолжается, поскольку сток 5 не помечен. Теперь сток помечен ( есть прорыв), и тем самым выделен путь 0 - - 1 - 5, по которому можно увеличивать поток. [7]
Алгоритм начинает работу с присвоения каждой вершине x Т, пометки [ а. Поскольку к Та добавлена новая вершина x то, может быть, придется изменить пометки [, В - ] у некоторых вершин x Т3 ( если, например, с, X ]) меньше существующей пометки Ву) и после этого продолжить процесс. Такая процедура расстановки пометок очень похожа на ту, которая используется в задаче о кратчайшем пути при применении алгоритма Дейкстры ( гл. [8]
На каждом шаге выполнения алгоритма вершина, например Xj, с наименьшей пометкой PJ присоединяется к Тв посредством добавления ребра ( a. Поскольку к Ts добавлена новая вершина я /, то, может быть, придется изменить пометки [ о -, р / ] у некоторых вершин xi s ( если, например, с ( х Xj) меньше существующей пометки Bj) и после этого продолжить процесс. Такая процедура расстановки пометок очень похожа на ту, которая используется в задаче о кратчайшем пути при применении алгоритма Дейкстры ( гл. [9]
Процедура расстановки пометок предназначена для выделения путей ( цепей) от источника к стоку, по которым можно увеличивать поток. Процедура изменения потока заключается в осуществлении этого увеличения. Добавим, что процедурой расстановки пометок устанавливаются также существование начального допустимого потока и оптимальность потока. Если сток помечен не до конца и больше пометки расставлять невозможно, то это признак того, что или допустимого потока нет, или после последнего изменения получен оптимальный поток. [10]
Если все нижние границы lij0, то в качестве начального потока можно принять нулевой ( иц0 для всех ( i, /) &4) или некоторый другой отличный от нуля поток, заданный из физических соображений. Полный поток формируется таким образом: по всем путям из 0 в я - - 1, все дуги которых не насыщены, поток увеличивается на величину min ( dj - иц), где минимум берется по всем дугам каждого из путей в отдельности. Полученный полный поток принимается за начальный, и к нему применяется процедура расстановки пометок для его увеличения. [11]
Однако при выполнении этого алгоритма может возникнуть такая ситуация, когда очередное кратчайшее ребро, выбранное из списка, построенного на шаге 2, будет соединять две вершины одного и того же поддерева. Поэтому на шаге 3, прежде чем добавлять ребро к графу Т, надо проверить, является ли оно допустимым в указанном выше смысле. Такую проверку можно выполнить более эффективно ( путем осуществления одного сравнения с использованием процедуры расстановки пометок, описанной в разд. [12]
Если сток оказался непомеченным ( произошел непрорыв), то просматриваются по очереди один за другим все 0-узлы. Если для фиксированного 0-узла NJ не существует дугового потока xkj 0, где Nk является 0-узлом, то узел NJ является отброшенным и просмотренным; он получает пометку ОП. После этого просматривают все соседние с N h 0-узлы и Н - узлы, ищутся среди них новые П - узлы и 0-узлы. Если все узлы имеют пометки ОП, ПП или Н, то процедура расстановки пометок прекращается. Если при этом Nt ( j X, то максимальный поток построен. [13]