пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» Сети ЭВМ

A

для всех узлов V; Если V смежный с А; D(v)=C(A,v) иначе D(v)=бесконечности.

Цикл: Найти W, не входящий в N, такой что D(W) минимальна. Добавить W к N. Обновить D(v) для всех v смежных с W и не входящих в N: D(v)=min(D(v), D(W), D(W,v)). По всем узлам в N.  

 

Алгоритм дистанционно-векторной марштуризации является распределенным, итерационным и асинхронным. Процесс продолжается пока соединенные узлы не перестают обмениваться информацией. Асинхронный поскольку не требует, чтобы все узлы работали в жесткой взаимосвязи. Каждый узел имеет свою таблицу расстояний, строка для адресата и столбец для каждого ближайшего соседа. Dx(y,z)=C(x,z)+minw(Dz(y,w)).

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

Алгоритм инициализация: Для всех всех смежных узлов V: Dx(*,v)=бесконечности // *-любой узел. Dx(v,v)=C(x,v).  Для всех адресатов Y- послать minwD(y,W) каждому соседу.

Цикл:

Ждать(пока не изменится стоимость ЛС с соседом v или пока не будет получено обновление от соседа v). Если (стоимость C(x,v) изменилась на d) /*изменение стоимости путей ко всем адресам через соседа v на величину d*/     /*d-может быть как положительным так и отрицательным*/  Для всех адресов Y:  Dx(y,v)= Dx(y,v)+d. Иначе если (получено обновление от v адресат Y)  /* изменение кратчайшего пути от v до Y */     /* Узел v послал новое значение minwDY (Y,W), назовем его newVal  */   для одного адресата y: Dx(Y,v)=C(x,v)+ newVal . Если получим новое значение  minwDX (Y,W) для Y  послать новое значение  minwDX (Y,W) всем соседям.   Конец цикла.


20.01.2014; 23:09
хиты: 55
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь