Для(4): Это можно доказать применив Лемму 4.1 . Получим что (если S’-путь от u в v существует) это простой S' -путь длиной dS’(u, v) от u к v, такой, что dS’(u, v) = min(dS (u, v), dS (u, w) + dS (w, v) ) по (3).
Для (5): каждый S-путь - путь, и обратно.
Для (6): каждый S-путь - путь, и обратно, следовательно, оптимальный V-путь также оптимальный путь.
_____________________________________________________________________
begin (* Инициализация S = Æ и D = Æ-дистанция *)
S:=0;
forall u,v do
if u = v then D[u, v] := 0
else
if uv Î E then D[u, v] := wuv
else D[u. v] := ¥ ;
(* Расширим S «центральными точками» *)
while S ¹ V do
(* Цикл инвариантен: "u, v : D[u, v] = dS (u, v) *)
begin выбрать w из V \ S ;
(* Выполнить глобальную w-центровку *)
forall u Î V do
(* Выполнить локальную w-центровку u *)
forall v ÎV do
D[u. v] := min ( D[u, v], D[u, w] + D[w, v] ) ;
S:=S È{w}
end (*"u, v : D[u, v] = dS (u, v)*)
end
Алгоритм4.4 Алгоритм Флойда-Уошалла.
Используя Утверждение 4.5 не сложно разработать алгоритм "динамического программирования" для решения проблемы кротчайших путей всех пар; смотри см. Алгоритм 4.4. Алгоритм вначале считает 0-пути, и, увеличивая, вычисляет S-пути для больших множеств S (увеличивая S "центральными" кругами), до тех пор, пока все пути не будут обсуждены.
Теорема 4.6 Алгоритм 4.4 вычисляет расстояние между всеми парами узлов за Q(N3) шагов.
Доказательство. Алгоритм начинает с D[u, v] = 0, если u = v, D[u, v] = wuv , если uv Î E и D[u, v] = ¥ в другом случае, и S = 0. Следуя из Утверждения 4.5, частей (1) и (2), "u, v имеет силу D[u, v] = dS (u, v) . В центральной окружности с центральной вершиной w множество S расширено узлом w, и означивание D[u, v] гарантирует (по частям (3) и (4) утверждения) что утверждение "u, v : D[u, v] = dS(u, v) сохранено как инвариант цикла. Программа заканчивает работу, когда S = V, т.е., (по частям (5) и (6) утверждения и инварианту цикла) S-расстояние эквивалентно расстоянию.
Главный цикл выполняется N раз, и содержит N2 операций (которые могут быть выполнены параллельно или последовательно), откуда и следует временная граница данная теоремой.ˆ
var Su : множество вершин;
Du : массив весов;
Nbu : массив вершин;
begin Su :=Æ ;
forall v Î V do
if v = u
then begin Du [v] :=0 ; 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 ;
(* Все вершины должны побывать вершиной w *)
if u == w
then "распространить таблицу Dw"
else "принять таблицу Dw"
if Du[w] + Dw[v] < Du[v] then
begin Du[v]:= Du[w] + Dw[v] ;
Nbu[v] := Nb[w]
end;
Su := Su U {w}
Алгоритм 4.5 Простой алгоритм (Для узла u).
4.2.2 Алгоритм кротчайшего пути.(Toueg)
Распределенный алгоритм вычисления таблиц маршрутизации бал дан Toueg [TouSOa], основанный на алгоритме Флойда-Уошалла описанном в предыдущей части. Можно проверить что алгоритм Флойда-Уошалла подходит для этих целей, т.е., что его ограничения реалистичны для распределенных систем. Наиболее важное ограничение алгоритма что граф не содержит циклов отрицательного веса. Это ограничение действительно реально для распределенных систем, где обычно каждый отдельный канал означен положительной оценкой. Даже можно дать более строгое ограничение; смотри A1 ниже. В этой части даны следующие ограничения.
A1. Каждый цикл в сети имеет положительный вес.
A2. Каждый узел в сети знает обо всех узлах (множество V).
A3. Каждый узел знает какой из узлов его сосед (хранится в Neighu для узла u) и веса своих выходящих каналов.
Корректность алгоритма Toueg (Алгоритма4.6) будет более просто понять если мы сперва обсудим предварительную версию алгоритма , "простой алгоритм" (Алгоритм 4.5).
Простой алгоритм. Для достижения распределенного алгоритма переменные и операции алгоритма Флойда-Уошала распределены по узлам сети. D[u, v] - переменная принадлежащая узлу u; по соглашению, это будет выражено описанием Du[v] .Операция, означивающая Du[v], должна быть выполнена узлам u, и когда необходимо значение переменной узла w, это значение должно быть послано u. В алгоритме Флойда-Уошала все узлы должны использовать информацию из «центрального» узла (w в теле цикла), который посылает эту информацию к всем узлам одновременно операцией "распространения". В заключение, алгоритм будет расширен операцией для поддержки не только длины кратчайших S-путей (как в переменной Du[v]), но также первый канал такого пути (в переменной Nbu[v]).
Утверждение что циклы сети имеет положительный вес может использоваться чтобы показать что не существует циклов в таблицах маршрутизации.
Лемма 4.7 Пусть даны S и w и выполняется:
(1) для всех u :Du[w] = dS(u, w) и
(2) если dS(u, w) < ¥ и u ¹ w, то Nbu[w]- первый канал кратчайшего S-пути к w.
Тогда направленный граф Tw = (Vw, Ew), где (u Î Vw Û Du[w]<¥ ) и (ux ÎEw Û (v¹wÙNbu[w]=x)) - дерево с дугами направленными к w.
Доказательство. Во-первых, заметим, что если Du[w] < ¥ для u ¹ w, то Nbu[w] ¹ udef и . Таким образом для каждого узла u Î Vw, u ¹ w существует узел x для которого Nbu[w] = x, и x Î Vw.
Для каждого узла u¹ w в Vw существует единственное ребро в Ew, такое что число узлов в Tw превышает количество ребер на единицу и достаточно показать что Tw не содержит циклов. Так ux ÎEw подразумевает что dS(u, w) =wux+ dS(x, w), существование цикла <uo, u1, .. ., uk> в Tw подразумевает что
dS(uo, w) = wuo u1 + wu1 u2 + … + wuk-1 uou+ dS(uo, w),
т.е., 0 = wuo u1 + wu1 u2 + … + wuk-1 uou
что противоречит предположению, что каждый цикл имеет положительный вес. ‰
Алгоритм Флойда-Уошала теперь может быть просто преобразован в Алгоритм 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.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
