Algorytmy

Johnsona, algorytm

  • 2006-04-13 19:45
  • 4 komentarze
  • 1720 odsłon
  • Oceń ten tekst jako pierwszy
Algorytm Johnsona ? dla grafów rzadkich, wykorzystujący działanie algorytmu Dijkstry i Bellmana - Forda jako podprogramów z zastosowaniem metody zmieniających się wag.


?        Opis zagadnienia

Algorytm Johnsona znajdowania najkrótszych ścieżek wykorzystuje działanie wcześniej opisanych algorytmów ? Dijkstry oraz Bellmana-Forda.
Istota algorytmu polega na zastosowaniu metody zmieniających się wag ? jeśli wszystkie wagi krawędzi w grafie G=(V, E) są nieujemne, wówczas najkrótsze ścieżki między wszystkimi parami wierzchołków wyznaczane są za pomocą algorytmu Dijkstry ? z każdego wierzchołka oddzielnie. Dla grafu o wagach ujemnych obliczyć należy nowy zbiór nieujemnych wag krawędzi, co umożliwi zastosowanie algorytmu Dijkstry. Wyliczony nowy zbiór wag ( ) musi spełniać zależności:


1.        Dla wszystkich par wierzchołków  najkrótsza ścieżka z wierzchołka u do v dla funkcji wagowej   jest także najkrótszą ścieżką pomiędzy tymi wierzchołkami, dla nowej funkcji wagowej  
2.        Dla wszystkich krawędzi grafu G, nowa waga  jest nieujemna.


Aby zmienić wagi krawędzi grafu, by spełniały one powyższe dwie własności wystarczy dla dla każdej krawędzi   grafu skierowanego G=(V, E) o funkcji wagowej  , zdefiniować zależność:

 

Gdzie  R to dowolna funkcja odwzorowująca wierzchołki grafu G=(V, E) w zbiór liczb rzeczywistych. Oznaczmy przez  wagi najkrótszych ścieżek przy funkcji wagowej  , natomiast przez  - wagi najkrótszych ścieżek przy funkcji wagowej  . Dla ścieżki  p=<v0, v1,?,="v1,?," vk="vk"> z wierzchołka v0 do vk funkcja  wtedy i tylko wtedy, gdy  . Wynika z tego również fakt, iż graf G=(V, E) ma cykl o ujemnej wadze przy funkcji wagowej   wtedy i tylko wtedy, gdy ma on także cykl o ujemnej wadze przy funkcji wagowej  .
 

?        Dane: graf G zapisany jako lista sąsiedztw

?        Wynik: Macierz wag najkrótszych ścieżek, lub informacja o tym, że graf wejściowy ma cykl o ujemnej wadze

?        Zapis algorytmu w pseudokodzie - brak


?        Dowód poprawności algorytmu  - brak


?        Zastosowanie
    Sterowanie procesami dyskretnymi
-        W planowaniu i kontroli produkcji
-        Algorytmy usuwania lewostronnej rekursji
-        Algorytm Johnsona dla procesów przepływowych 2 i 3 magazynowych
-        Szeregowanie operacji dla linii produkcyjnej


?        Złożoność obliczeniowa
Stosując kopce Fibonacciego do implementacji kolejki priorytetowej otrzymać można algorytm działający w czasie O(V2 lg V + VE).
Wstępne przetworzenie grafu G w celu obliczenia nowej nieujemnej funkcji wagowej   jest możliwe do wykonania w czasie O(VE)</br>

4 komentarze

omer19 2006-04-27 23:25

chyba wazniejsza jest treść...

Marooned 2006-04-15 01:06

Poprawić wygląd?

Adam Boduch 2006-04-14 13:37

Heh, no i co z tym zrobic? :|