Цикл: Найти 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) всем соседям. Конец цикла.