Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 35
Текст из файла (страница 35)
Для всех вершин и и подмножеств S верно неравенство ds (u, и) ^ 0, потому что пустой путь (не содержащий ни одного ребра)является S -путем из и в и веса 0. Никакой другой путь не имеет меньшего веса,поскольку в графе G нет циклов отрицательного веса. Значит, ds (u, и) = 0.Правило (1). Так как 0-путь не имеет промежуточных вершин, 0-путь из ив v состоит только из канала uv.Правило (2). Следует непосредственно из правила 1).Правило (3). В простом S '-пути из и в v вершина да либо встречается ровноодин раз, либо вообще не встречается.
Если не содержит промежуточной вершины да, то это S -путь; в противном случае этот путь представляет собой последовательное соединение двух S -путей, один из которых ведет в вершину да, адругой исходит из вершины да.Правило (4). Применяя лемму 4.1, можно показать, что в том случае, еслив графе есть S '-путь из и в о, существует и простой S '-путь длины ds (и, v) из ив V. Согласно правилу (3) отсюда следует равенство ds (и, v) = min ( ds (u, v), ds (u, w)+ds (Правило (5). Каждый К-путь является путем и наоборот.4.2. Задача построения кратчайших путей для всех пар вершин125Правило (6). Каждый К-путь является путем и наоборот.
Поэтому оптимальный К-путь также является оптимальным путем.□begin(* Вначале положить S равным 0, a D считать равной 0-расстоянию *)S := 0 ;forallи, v doif и = v then D[u, v\ := Оelse if uv € E then D[u, v] := couvelse D[u, v] := oo ;(* Добавить к S «центровую» вершину*)while S ДVdo(* Инвариант цикла: Vm, v : D[u, a] = ds (u, v) *)begin pick да from V \ S ;(* Выполнить глобальную обработку опорной вершины да *)forallu eVdo(* Выполнить локальную обработку опорной вершины да для и *)forallv е V doD[u, v] := min (D[u, о], D[u, да] + D[w, ц ] ) ;S := S U {да}end (* Vm,v: D [u, o] = d(u,v)*)Алгоритм 4.4.
Алгоритм Флойда— Уоршалла*SПри помощи утверждения 4.5 и метода динамического программированиянетрудно разработать алгоритм решения задачи построения кратчайших путейдля всех пар вершин (см. алгоритм 4.4). В этом алгоритме сначала рассматриваются 0-пути, а затем последовательно строятся S -пути для расширяющихсямножеств S, до тех пор пока не будут рассмотрены все пути.Теорема 4.6. Алгоритм 4.4 вычисляет расстояние между всеми парамивершин за 0(А 3) шагов.Д о к а з а т е л ь с т в о .
В начале работы алгоритма D[u, и] = 0, если и == v, D[u, v ] = toцо, если uv € Е, и D[u, v] = оо в остальных случаях. При этомS = 0. Согласно правилам 1) и 2) утверждения 4.5 мы имеем Vm, v : D[u, v] == ds (u, v). Если к множеству S добавляется вершина w, то согласно правилам 3)и 4) того же утверждения оператор присваивания, уточняющий значение D[u, и],обеспечивает сохранение выполнимости предложения Vm, v : D[u, v] = ds (u, v),используемого в качестве инварианта цикла. Программа завершает выполнение,когда S = V.
Принимая во внимание правила 5) и 6) утверждения 4.5, а такжеинвариант цикла, заключаем, что S -расстояния между всеми вершинами равнырасстояниям.Основной цикл выполняется N раз, и в каждой его итерации выполняетсяv)f!2 операций (их можно выполнять последовательно или параллельно). Отсюдаполучается верхняя оценка сложности алгоритма.□Гл. 4. Алгоритмы маршрутизации1264 .2 .2 . А л г о р и т м Т у э г а п о с т р о е н и я к р а т ч а й ш и х п у т е йvar SuDuNbu'■set °f nodes ;: array of weights ;: array of nodes ;begin S„ := 0 ;forall v € V doif v = иthen begin D u [v\ := 0 ; N b u [v] := u d e f endelse if и € N e i g h uthen begin D u [v] := <auv ; N b u [v\ := v endelse begin D u [v\ := oo ; N b u [v] := u d e f end;while S u У У dobegin pick w from V \ S u ;(* Здесь все процессы должны выбрать о д н уи т у жевершину w *)if и = wthen «broadcast the table D w »else «receive the table D w » ;forall v € V doif D u [w ] + D w [v] < D u [v\ thenbegin D u [v] := D u [w ] + D w [v\ ;N b u [ v ] := N b u [w ]end;Su := Su U {ay}endendАлгоритм 4.5.
Упрощенный вариант алгоритма (для узлаи).Распределенный алгоритм вычисления таблиц маршрутизации был разработан Туэгом в работе [194] на основе алгоритма Флойда—Уоршалла, которыйбыл описан в предыдущем параграфе. Мы должны убедиться в том, что алгоритм Флойда—Уоршалла подходит для этой цели, т. е. те допущения, на которыхбазируется этот алгоритм, верны для распределенных систем.
Наиболее важным из этих допущений является предположение о том, что в графе нет цикловотрицательного веса. Распределенные системы и в самом деле обладают этимсвойством, так как каждому отдельному каналу связи приписывается положительная стоимость. Можно принять даже более строгое предположение (см. А1ниже).В этом параграфе мы будем действовать в рамках следующих допущений.А1. Каждый цикл в сети имеет положительный вес.А2.
Каждый процесс сети располагает информацией об отличительных признаках всех узлов системы (множества вершин V).4.2. Задача построения кратчайших путей для всех пар вершин127АЗ. Каждый процесс располагает информацией о том, какие узлы являютсяего соседями (для каждой вершины и эти сведения содержатся в массиве Neighu)и какой вес имеют каналы, соединяющие процесс с его соседями.Нам будет проще разобраться с корректностью алгоритма Туэга (алгоритм 4.6),если вначале мы рассмотрим его упрощенный вариант, так называемый «простойалгоритм» (алгоритм 4.5).Упрощенный алгоритм. Чтобы получить распределенный алгоритм, переменные и операции алгоритма Флойда—Уоршалла разносятся по разным узлам сети.
Переменная D[u, v] отдается процессу и; для удобства обозначениямы будем записывать и на месте индекса следующим образом Du[v], Операции,которые присваивают значения переменной Du[v], должны выполняться в узлеи, и, когда значение некоторой переменной, относящейся к узлу да, необходимодля этой операции, это значение должно быть послано процессу и. В алгоритмеФлойда—Уоршалла все вершины должны использовать информацию от опорной вершины (она обозначена символом да в теле цикла), которая отправляет этуинформацию одновременно всем вершинам посредством «широковещательной»операции. Наконец, в этом алгоритме нужно ввести специальную операцию, длятого чтобы не только вычислять длины кратчайших S -путей (для этого используются переменные Du[v]), но также и первый канал в каждом таком пути (дляэтого мы будем использовать переменные Nbu[v]).Допущение о том, что всякий цикл в сети имеет положительный вес, можно использовать для того, чтобы показать, что после каждого этапа обработкиопорной вершины в таблицах маршрутизации не образуются циклы.Лемма 4.7.
Пусть заданы множество вершин S и вершина да. Предположим также, что1) для всех вершин и верно равенство Du[w] = ds (u, да);2) если ds (u, да) < оо и и Ф да, то значением переменной Nbu[w] является имя соседа вершины и на кратчайшем S-nym u, ведущем к вершине да.Тогда ориентированный граф Tw = (Vw, Ew), где( u e V w -4=^ Du[w\ < оо)и{их е Еш -4=^ ( а / д а Д Nbu[w] = х)),является деревом, в корне которого расположена вершина да.Д о к а з а т е л ь с т в о . Прежде всего заметим, что в том случае, если длявершины и Ф да выполняется неравенство /) ц[да] < оо, то Nbu\w] Ф udef иDmu\w][да] < оо. Значит, для каждой вершины u e Vw, и ф т , существует вершинах, х е Vw, для которой верно равенство Nba[w] = х.Для каждой вершины иЕ Vw, и Ф да, в множестве Еш есть одно ребро, и поэтому число вершин в графе Тш превосходит количество ребер на единицу.
Осталосьпоказать, что граф Тш не содержит циклов. Коль скоро для ребра их Е Ew имеет место равенство ds (u, да) = <s>ux + ds {x, да), наличие цикла («о, и\, ... , ифв графе Tw повлекло бы за собой следующее соотношение:ds {uq, да)йи0щ += се ) Ц1ц2 + . . .
+и>ик_1Щ) + ds (uo,да),128Гл. 4. Алгоритмы маршрутизациииз которого вытекает то, чтоО = coUoUl + coUlu2 + . . . + e)U/i_ lUo,а это противоречит допущению о том, что каждый цикл имеет положительныйвес.□Теперь алгоритм Флойда—Уоршалла может быть непосредственно преобразован в алгоритм 4.5. Каждая вершина-процесс устанавливает начальные значения приписанным ей переменным и выполняет N итераций основного цикла. Этоталгоритм еще не дает нам окончательного решения, потому что мы не описали,как провести эффективное широковещательное распространение таблицы маршрутизации опорной вершины. Пока мы можем лишь поверить, что в том случае,когда операция «broadcast the table Dw» выполняется процессом w, а операция«receive the table Dw» выполняется другими процессами, каждый узел получитдоступ к таблице Dw.Нужно обратить особое внимание на операцию «pick w from V \ S» и организовать ее выполнение так, чтобы все процессы выбирали опорные вершиныв одном и том же порядке.
Коль скоро предполагается, что всем процессам заранее известно множество V, мы можем считать, что вершины из этого множествавыбираются в каком-либо заранее заданном порядке (например, имена вершинвыбираются в алфавитном порядке).Корректность упрощенного алгоритма устанавливается в следующей теореме.Теорема 4.8. Алгоритм 4.5 завершает свое выполнение в каждом узлесети после N итераций основного цикла. Когда алгоритм завершаетсяв узле и, для каждой вершины v выполняется равенство Du[v] = d(u, v ),и в том случае, если в сети есть путь из и в и, то значением переменнойNbu[v] является наименование первого канала в кратчайшем пути из ив у; в противном случае Nbu[v] = udef.Д о к а з а т е л ь с т в о .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
