1) Определение рангов событий, которые позволяют осуществить правильную нумерацию вершин. Это сокращает трудоёмкость вычисления рам и позднейших времён наступления событий.
Опр. Рангом Ri события (вершины) i называется максимальное число дуг в пути из входной 1 в вершину i.
Ранги событий находят по рекурсивной формуле:
| Rk(j)= | { | 0, i=1; |
| max { Rk(j)+1 |j € S, i≠1}, где |
k(j) – концевая вершина;
S –множество работ (дуг), S = {1,…n}.
Алгоритм Форда для вычисления рангов событий(вершин)
Шаг 0. Полагаем Ri =0 V i =1,…,m. Пусть в результате (k-1) шагов найдено Ri.
Шаг k. Просматривая последовательностно дуги (работы) j=1,…,n вычисляем
Rk(j) = max { Rk(j), Rk(j)+1},
где Rk(j) концевая вершина дуги j.
Если на очередном шаге ранги всех вершин сети не изменились, алгоритм завершает свою работу. Иначе k = k+1 и повторить шаг k.
Сложность алгоритма T = O(m*n).
| события | ранги | Шаг 0 | Шаг 1 | Шаг 2 |