DSC00304 (9)

10,3. OROOl PROSTE, ■KmUlMAt.Nt W SIECIACH CYKLICZNYCH

10.3.1. Algorytm wyznaczania maksymalnego dendrytn dróg najkrótszych Dane

Siei S*(G, 0, {/}), dia której bądź 0, bądź wszystkie drogi cykliczne w niej zawarte mają nieujemną długość. Ustalony wierzchołek x*.

Procedura

Będziemy cechować wierzchołki podwójnymi cechami (F(x),g(x)) zmniejszając iteracyjnie wartości F{x).

1.    Wierzchołkowi x* nadajemy cechą podwójną (0, +), a pozostałym wierzchołkom sieci cechy (oo, +).

2.    Zmniejszamy iteracyjnie wartości lewych cech F(x) wierzchołków różnych od x* w następujący sposób:

Dla łuków u«(x,y) digrafu G takich, Ze

F(y)-F(x)>l«x,y»

nadajemy wartość lewej cechy wierzchołka y równą F(y) ^m F(x)+l«x] y»

Jako wartość prawej cechy g(y) wierzchołka y wpisujemy numer wierzchołka x, z którego nadano nową wartość lewej cechy wierzchołkowi y. Czynności opisane w tym punkcie kontynuujemy, sprawdzając wszystkie luki po kaZdej zmianie cechy, dotąd aż nie będzie można zmniejszyć lewej cechy żadnego wierzchołka.

3.    Tworzymy maksymalny dendryt najkrótszych dróg prostych w ten

sposób, że do każdego wierzchołka y doprowadzamy jeden łuk od poprzednika x ■» g (y). Do dendrytu wejdą wszystkie wierzchołki o cechach różnych od (oo, +), Długości dróg    *A równe ostatnim ce

chom F(x).

Uwaga I. W danej sieci S, od ustalonego wierzchołka x*, może istnieć wiele różnych dróg najkrótszych do pewnego wierzchołka x. Przedstawiony algorytm wyznacza tylko jedną z tych dróg (przypadkowo wybraną w wyniku przypadkowej kolejności zmniejszania lewych cech, wierzchołków).

Uwaga 2. Algorytm charakteryzuje się wielokrotnym, itcraćyjnytn cechowaniem wierzchołków. Jeżeli-zatem występuje w praktyce potrzeba wyznaczania tylko jednej drogi najkrótszej, łączącej ustaloną parę wierzchołków |p x*)t to nie możemy przerwać procesu cechowania z chwilą pierwszego zmniejszenia cechy F(x^k). Procedura punktu 2 algorytmu musi być kontynuowana do końca i dopiero wtedy zamiast całego dendrytu możemy wyznaczyć tę jedną poszukiwaną drogę według prawych cech wierzchołków g(x).

Uwaga 3. W porównaniu z algorytmami stosowanymi dla sieci acyklicznych, opracowany algorytm ma znacznie mniejszą efektywność. Ilość niezbędnych obliczeń rośnie bardzo szybko ze wzrostem liczby wierzchołków sieci.