DSC00303 (8)

ip.ł. DROPI PROSTR. BK3TKBMAŁNB W SIECIACH ACYKLICZNYCH

10.2.1. Algorytm wyznaczania maksymalnego dendryta dróg najdłuższych Dant

Sieć skierowana bez dróg cyklicznych o postaci:

$*<(?. 0,{/}>, C7-<»',r>; r:W-2^W\ ŃŚ*R;

U^m{<x,y):(x, y*W)A(y*rx)}; x^p— wierzchołek początkowy (korzeń dendrytu).

Proceduro

1.    Wyznaczamy warstwy digrafu G: JV₀, W_it, W_t. Oznaczamy przez i numer warstwy, do której należy wierzchołek x’\ x*e W_t. K — oznacza numer ostatniej warstwy.

2.    Będziemy cechowali wierzchołki xefV cechami podwójnymi (F(x), g(x)).' W tym celu przez C oznaczymy zbiór wierzchołków, które są aktualnie ocechowane. Zadanemu wierzchołkowi x^p nadajemy cechę (0, 0), to znaczy F(x^f) -»0/g(xO «■ 0. W tej chwili C— {x^p). Podstawiamy i««i +1.

3.    Pytamy: czy i>Kl

NIE: Bierzemy pod uwagę warstwę W_t (następną w kolejności) oraz takie wierzchołki xeW,, dla których zbiór ocechowanych poprzedników nie jest pusty, /'J¹ r\C # 0. Dla każdego wierzchołka xe W_lt którego zbiór ocechowanych poprzedników nie jest pusty, obliczamy wartość lewej cechy

/■(*)« max [l(y, x)+F(y)]

Jako wartość prawej cechy g(x) wierzchołka * przyjmujemy ten wierzchołek y, przy którym powyższe wyrażenie przyjęło wartość ekstremalną.

C«Cu{x}

Po rozpatrzeniu wszystkich wierzchołków xe W_x podstawiamy ii-ł + 1 i przechodzimy do punktu 3.

;TAK: Przechodzimy do punktu 4 (rozpatrzone zostały wszystkie warstwy).

4.    Zbiór ocechowanych wierzchołków C jest zbiorem wierzchołków osiągalnych z wierzchołka x*, to znaczy stanowi zbiór wierzchołków maksymalnego dendrytu najdłuższych dróg, wychodzących z wierzchołka x^p, w sieci S. Długość najdłuższej drogi z x^p do dowolnego wierzchołka xeC określona jest wartością lewej cechy F(x) tego wierzchołka. Drogę tę wyznaczają prawe cechy wierzchołków, poczynając od wierzchołka x i przesuwając się do wierzchołka x’_t przeciwnie do zwrotu łuków (od końca). Znajdując w ten sposób antydrogi do wierzchołka x* dla każdego wierzchołka x«C, wyznaczamy cały dendryt maksymalny najdłuższych dróg w sieci S, od zadanego wierzchołka x^p, Praktycznie należy do każdego wierzchołka x doprowadzić jeden łuk od wierzchołka określonego wartością prawej cechy g(x).