Алгоритм Форда

Шаг 0. Полагаем R_i =0, i=1,…,6.

Шаг 1. Последовательностно просматриваем дуги (работы) и пересчитываем ранги их концевых вершин:

S = 1 ð (1, 2): R₂ = max {R₂, R₁ +1} = max {0, 0+1} = 1;

S = 2 ð (1, 6): R₆ = max {R₆, R₁ +1} = max {0, 0+1} = 1;

S = 3 ð (2, 3): R₃ = max {R₃, R₂ +1} = max {0, 1+1} = 2;

S = 4 ð (3, 4): R₄ = max {R₄, R₃ +1} = max {0, 2+1} = 3;

S = 5 ð (4, 5): R₅ = max {R₅, R₄ +1} = max {0, 3+1} = 4;

S = 6 ð (6, 4): R₄ = max {R₄, R₆ +1} = max {3, 1+1} = 3;

S = 7 ð (6, 3): R₃ = max {R₃, R₆ +1} = max {2, 1+1} = 2.

 

Шаг 2

S = 1 ð (1, 2): R₂ = max {R₂, R₁ +1} = max {0, 1+1} = 1;

S = 2 ð (1, 6): R₆ = max {R₆, R₁ +1} = max {1, 0+1} = 1;

S = 3 ð (2, 3): R₃ = max {R₃, R₂ +1} = max {2, 1+1} = 2;

S = 4 ð (3, 4): R₄ = max {R₄, R₃ +1} = max {3, 2+1} = 3;

S = 5 ð (4, 5): R₅ = max {R₅, R₄ +1} = max {4, 3+1} = 4;

S = 6 ð (6, 4): R₄ = max {R₄, R₆ +1} = max {3, 1+1} = 3;

S = 7 ð (6, 3): R₃ = max {R₃, R₆ +1} = max {2, 1+1} = 2.

Конец работы алгоритма, т.к. значения на шаге 2 совпадают со значениями на шаге 1.

Получили ранги событий:

R₁ =0; R₂ =1; R₃ =2; R₄ =3; R₅ =4; R₆ =1.

Опр Нумерация сети правильная, если i(j) < k(j) для каждой дуги (работы) j = 1,…,n.

Правильная нумерация:

Ø Вход (вершина нулевого ранга) ð 1;

Ø Вершинам ранга 1 ð 2,…,m₁;

Ø Вершинам ранга 2 ð m₁+1,…,m₂ и т.д.

Ø Выход сети ð m.