Сети ЭВМ и телекоммуникации. Архитектура и сетевые технологии. Анкудинов Г.И - 94 стр.

UptoLike

Составители:

Рубрика:

Шаги алгоритма:

1. Устанавливаем множество узлов N = {A}.

2. Для каждого узла j∉N устанавливаем d (j) = r (A, j).

3. Для каждого шага находим узел k∉N, для которого d(k) минимально, фиксируем

соответствующую дугу (i,k) и добавляем k в множество N.

4. Для всех узлов j∉N находим оценку d (j) = min{ d

(j), d (j)+ r (k, j)}.

5. Шаги 2-4 повторяются до тех пор, пока все узлы не окажутся в множестве N.

Таблица 5.1

r(i,j) Шаг Дуга Множество N

B C D E F G

1 - {A} 4 3 2 - - -

2 AD {A,D} 4 3 (2) 6 7 8

3 AC {A,D,C} 4 (3) 2 6 5 8

4 AB {A,D,C,B} (4) 3 2 5 5 8

5 BE {A,D,C,B,E} 4 3 2 (5) 5 8

6 CF {A,D,C,B,E,F} 4 3 2 5 (5) 8

7 FG {A,D,C,B,E,F,G} 4 3 2 5 5 (7)

Порядок вычислений для рассматриваемого примера приведен в табл. 5.1. На рис.

5.5 приведена топология маршрутов для узла A, составленная из дуг (i,k),

зафиксированных на каждом шаге.

Рис.5.4

4 4

3 4

A D

B E