что противоречит предположению, что каждый цикл имеет положительный вес.
Алгоритм Флойда-Уошала теперь может быть просто преобразован в Алгоритм 4.5. Каждый узел инициализирует свои собственные переменные и исполняет N итераций основного цикла. Этот алгоритм не является окончательным решением, и он не дан полностью, потому что мы не описали, как может бать произведено (эффективно) распространение таблиц центрального узла. Пока это можно использовать как гарантированное, поскольку операция "распространить таблицу Dw" выполняется узлом w, а операция "принять таблицу Dw" выполняется другими узлами, и каждый узел имеет доступ к таблице Dw.
Некоторое внимание должно быть уделено операции "выбрать w из V \ S", чтобы узлы выбирали центры в однообразном порядке. Так как все узлы знают V заранее, мы можем запросто предположить, что узлы выбираются в некотором предписанном порядке (на пример, алфавитный порядок имен узлов).
Корректность простого алгоритма доказана в следующей теореме.
Теорема 4.8 Алгоритм 4.5 завершит свою работу в каждом узле после N итераций основного цикла. Когда алгоритм завершит свою работу в узле u Du[v] = d(u, v), и если путь из u в v существует то Nbu[v] первый канал кротчайшего пути из u в v, иначе Nbu[v] = udef.
Доказательство. Завершение и корректность Du[v] по завершении работы следует из корректности алгоритма Флойда-Уошала (теорема 4.6). Утверждение о значении Nbu[v] справедливо потому что Nbu[v] перевычисляется каждый раз когда означивается Du[v] .
Усовершенствованный алгоритм. Чтобы сделать распространение в Алгоритме 4.5 эффективным, Toueg заметил, что узел u для каждого Du[w] = ¥ на старте w-централизованного обхода не меняет свои таблицы в течение всего w-централизованного обхода. Если Du[w] = ¥ , то Du[w] + Dw[v] < Du[v] не выполняется для каждого узда v. Следовательно, только узлы, принадлежащие Tw (в начале w-централизованного обхода) нуждаются в получении таблиц w, и операция распространения может стать более эффективной рассылая Dw только через каналы, принадлежащие дереву Tw. Таким образом, w рассылает Dw своим сыновьям в Tw и каждый узел в Tw который принимает таблицу (от своего отца в Tw) пересылает её к своим сыновьям в Tw.
____________________________________________________________________
var Su: множество узлов ;
Du: массив весов;
Nbu : массив узлов ;
begin
Su := Æ ;
forall v Î V do
if v = u
then begin Du[v] := O ; Nbu[v] := udef end
else if v Î Neighu
then begin Du[v] := wuv ; Nbu[v] := v end
else begin Du[v] := ¥ ; Nbu[v] := udef end ;
while Su¹ V do
begin выбрать w из V \ Su ;
(* Построение дерева Tw *)
forall x Î Neighu do
if Nbu[w] = x then send < ys, w> to x
else send < nys, w > to x ;
num_recu := O ; (* u должен получить |Neighu| сообщений *)
while num_recu < |Neighu| do
begin получить < ys, w > или < nys, w > сообщение ;
num_recu := num_recu + 1
end;
if Du[w] < ¥ then (* участвует в центр. обходе*)
begin if u¹ w
then получить <dtab,w,D> от Nbu[w] ;
forall x Î Neighu do
if < ys, w > было послано от x
then послать < dtab, w, D>) к x; ;
forall v Î V do (* локальный w-центр *)
if Du[w] + D[v] < Du[v] then
begin Du[v] := Du[w] + D[v] :
Nbu[v] := Nbu[w]
end
end;
Su := Su È {w}
end
end
Алгоритм 4.6 Алгоритм Тoueg (для узла u).
_____________________________________________________________________
В начале w-централизованного раунда узел u с Du[w] < ¥ знает кто его отец (в Tw) , но не знает кто его сыновья. Поэтому каждый узел v должен послать сообщение к каждому своему соседу u, спрашивая u является ли v сыном u в Tw. Полный алгоритм дан как Алгоритм 4.6. Узел может участвовать в пересылке таблицы w когда известно что его соседи являются его сыновьями в Tw. Алгоритм использует три типа сообщений:
(1) <ys,w> сообщение <ys обозначение для "your son"> u посылает к x; в начале w-централизованного обхода если x отец u в Tw.
(2) <nys, w> сообщение <nys обозначение для "not your son"> u посылает x в начале w-централизованного обхода если x не отец u в Tw
(3) <dtab, w, D> сообщение посылается в течение w-централизованного обхода через каждое ребро Tw чтобы переслать значение Dw к каждому узлу который должен использовать это значение.
Полагая сто вес (ребра или пути) вместе с именем узла можно представить W битами, сложность алгоритма показана следующей теоремой.
Теорема 4.9 Алгоритм 4.6 вычисляет для каждых u и v дистанцию от u к v, и, если эта дистанция конечная, первый канал. Алгоритм обменивается 0(N) сообщениями на канал,, 0(N*|E|) сообщений всего, O(N2W) бит на канал, O(N 3W) бит всего, и требуется 0(NW) бит хранения на узел.
Доказательство. Алгоритм 4.6 выведен от Алгоритма 4.5, который корректен.
Каждый канал переносит два ( < ys, w> или < nys, w> ) сообщений (одно в каждом направлении) и не более одного <dtab, w, D > сообщения в w-централизованном обходе, который включает не более 3N сообщений на канал. < ys, w > или < nys, w > сообщение содержит O(W) бит и <dtab, w, D > сообщение содержит O(NW) бит, что и является границей для числа бит на канал. Не более N2 < dtab, w,D> сообщений и 2N - |E| (<ys,w> и <nys,w> ) сообщений обмена, и того всего O(N2 - NW +2N-|E|-W) = O(N3W) бит. Таблицы Du и Nbu хранящиеся в узле u требуют 0(NW) бит.
В течение w-центализованного обхода узлу разрешено принимать и обрабатывать сообщения только данного обхода, т.е., те которые переносят параметр w. Если каналы удовлетворяют дисциплине FIFO тогда сообщения <ys,w> и <nys, w> прибывают первыми, по одному через каждый канал, и затем сообщение < dtab, w, D > от Nbu[ w] (если узел в Vw). Таким образом возможно, аккуратно программируя, опустить параметр w во всех сообщениях если каналы удовлетворяют дисциплине FIFO. Если каналы не удовлетворяют дисциплине FIFO возможно что сообщение с параметром w' придет пока узел ожидает сообщения для обхода w, тогда как w' становится центром после w. В этом случае параметр используется чтобы различить сообщения для каждого централизованного обхода, и локальная буферизация ( в канале и узле) должна использоваться для отсрочки выполнения w'-сообщения.
Toueg дал дальнейшую оптимизацию алгоритма, полагаясь на следующий результат. (Узел u2 потомок u1 если u2 принадлежит поддереву u1)
Лемма 4.10 Пусть u1¹ w, и пусть u2 потомок u1 в Tw, в начале w-централизованного обхода, если u2 изменит своё расстояние до v во время w-централизованного обхода, тогда и u1 изменит своё расстояние до v в этом же обходе.
Доказательство. Так как u2 потомок u1 в Tw :
dS(u2, w) = dS (u2, u1) + dS (u1, w). (1)
Так как u1 Î S:
dS(u2, v) £ dS (u2, u1) + dS (u1,v). (2)
Узел u2 изменит Du2 [v] в данном обходе тогда и только тогда когда
dS(u2, w) + dS (w, v) < dS (u2, v). (3)
Применяя (2), и затем (1), и вычитая dS(u2, u1), мы получим
dS(u1, w) + dS (w, v) < dS (u1, v) (4)
значит u1 изменит Du1 [v] в этом обходе.
В соответствии с этой леммой, Алгоритм 4.6 может быть модифицирован следующим образом. После получения таблицы Dw, (сообщение <dtab, w,D>) узел u вначале выполняет локальные w-централизованные операции, и затем рассылает таблицы своим сыновьям в Tw. Когда пересылка таблицы закончилась достаточно переслать те ссылки D[v] для которых Du[v] изменилась в течение локальной w-централизованной операции. С этой модификацией таблицы маршрутизации не содержат циклов не только между централизованными обходами (как сказано в Лемме 4.7), но также в течение централизованных обходов.
4.2.3 Обсуждение и Дополнительные Алгоритмы
Представление алгоритм Toueg предоставило пример как распределенный алгоритм может быть получен непосредственным образом из последовательного алгоритма. Переменные последовательного алгоритма распределены по процессам, и любое означивание переменной x (в последовательном алгоритме) выполняется процессом владеющим x. Всякий раз когда ознaчивающее выражение содержит ссылки на переменные из других процессов, связь между процессами потребуется для передачи значения и синхронизации процессов. Специфические свойства последовательного алгоритма могут быть использованы для минимизации числа соединений.
Алгоритм Toueg прост для понимания, имеет низкую сложность, и маршрутизирует через оптимальные пути; его главный недостаток в его плохая живучесть. Когда топология сети изменилась все вычисления должны произвестись заново.