Johnsona, algorytm

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,?, 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>