Algorytm Johnsona

Algorytm Johnsona

Klasa	Problem najkrótszej ścieżki dla wszystkich par (dla grafów ważonych)
Struktura danych	Wykres
Wydajność w najgorszym przypadku	${\ Displaystyle O (| V | ^ {2} \ log | V | + | V | | E |)}$

Aby zapoznać się z algorytmem planowania o tej samej nazwie, zobacz Planowanie warsztatu pracy .

Algorytm Johnsona to sposób na znalezienie najkrótszych ścieżek między wszystkimi parami wierzchołków w grafie skierowanym ważonym krawędziami . Pozwala, aby niektóre wagi krawędzi były liczbami ujemnymi , ale nie mogą istnieć żadne cykle z ujemnymi wagami . Działa przy użyciu algorytmu Bellmana-Forda do obliczenia transformacji wykresu wejściowego, która usuwa wszystkie ujemne wagi, umożliwiając użycie algorytmu Dijkstry na przekształconym wykresie. Został nazwany na cześć Donalda B. Johnsona , który jako pierwszy opublikował tę technikę w 1977 roku.

Podobna technika ponownego ważenia jest również używana w algorytmie Suurballe'a do znajdowania dwóch rozłącznych ścieżek o minimalnej całkowitej długości między tymi samymi dwoma wierzchołkami na grafie z nieujemnymi wagami krawędzi.

Opis algorytmu

Algorytm Johnsona składa się z następujących kroków:

1. do grafu dodawany jest nowy węzeł q , połączony krawędziami o zerowej wadze z każdym z pozostałych węzłów.
2. Po drugie, algorytm Bellmana-Forda jest używany, zaczynając od nowego wierzchołka q , aby znaleźć dla każdego wierzchołka v minimalną wagę h ( v ) ścieżki od q do v . Jeśli ten krok wykryje ujemny cykl, algorytm zostanie zakończony.
3. Następnie krawędzie oryginalnego wykresu są ponownie ważone przy użyciu wartości obliczonych przez algorytm Bellmana – Forda: krawędź od u do v , mająca długość , ${\ Displaystyle w (u, v)}$ nowy w długość w ( u , v ) + godz ( u ) - godz ( v ) .
4. Na koniec q jest usuwane, a algorytm Dijkstry jest używany do znajdowania najkrótszych ścieżek z każdego węzła s do każdego innego wierzchołka w ponownie zważonym grafie. Odległość na oryginalnym wykresie jest następnie obliczana dla każdej odległości D ( u , v ), dodając h ( v ) - h ( u ) do odległości zwróconej przez algorytm Dijkstry.

Przykład

Pierwsze trzy etapy algorytmu Johnsona przedstawiono na poniższej ilustracji.

Wykres po lewej stronie ilustracji ma dwie ujemne krawędzie, ale nie ma ujemnych cykli. Środkowy wykres przedstawia nowy wierzchołek q , najkrótsze drzewo ścieżek obliczone algorytmem Bellmana-Forda z q jako wierzchołkiem początkowym i wartościami h ( v ) obliczonymi w każdym innym węźle jako długość najkrótszej ścieżki od q do tego węzeł. Zauważ, że wszystkie te wartości nie są dodatnie, ponieważ q ma zerową długość krawędzi do każdego wierzchołka, a najkrótsza ścieżka nie może być dłuższa niż ta krawędź. w Po prawej stronie pokazano przeważony wykres utworzony przez ) + ( u ) h ( v ) każdej $zastąpienie$ wagi krawędzi przez . W tym przeważonym grafie wszystkie wagi krawędzi są nieujemne, ale najkrótsza ścieżka między dowolnymi dwoma węzłami wykorzystuje tę samą sekwencję krawędzi, co najkrótsza ścieżka między tymi samymi dwoma węzłami na oryginalnym grafie. Algorytm kończy się zastosowaniem algorytmu Dijkstry do każdego z czterech początkowych węzłów na ponownie ważonym grafie.

Poprawność

Na grafie z przewagą wszystkie ścieżki pomiędzy parą s i t węzłów mają dodaną taką samą ilość h ( s ) − h ( t ) . Poprzednie stwierdzenie można udowodnić w następujący $ścieżką$ p będzie . Jego waga W na przeważonym wykresie jest wyrażona następującym wyrażeniem:

${\ Displaystyle {\ bigl (} w (s, p_ {1}) + h (s) -h (p_ {1}) {\ bigr)} + ​​{\ bigl (} w (p_ {1}, p_ { 2})+h(p_{1})-h(p_{2}){\bigr )}+...+{\bigl (}w(p_{n},t)+h(p_{n} )-h(t){\bigr )}.}$

+ $p_ {i})}$ jest anulowane przez ${\ Displaystyle -h (p_ {i})}$ w poprzednim wyrażeniu w nawiasach; dlatego pozostaje nam następujące wyrażenie dla W :

$\ bigl (} w ( s,p_{1})+w(p_{1},p_{2})+...+w(p_{n},t){\bigr )}+h(s)-h(t)}$

Wyrażenie w nawiasach to waga p w oryginalnym ważeniu.

Ponieważ ponowne ważenie dodaje taką samą ilość do wagi każdej $.$ ścieżka jest najkrótszą ścieżką w pierwotnym ważeniu wtedy i tylko wtedy, gdy jest najkrótszą ścieżką po ponownym Waga krawędzi należących do najkrótszej ścieżki od q do dowolnego węzła wynosi zero, a zatem długości najkrótszych ścieżek od q do każdego węzła stają się zerem na grafie przeważonym; jednak nadal pozostają najkrótszymi ścieżkami. Dlatego nie może być ujemnych krawędzi: jeśli edge uv miał ujemną wagę po ponownym zważeniu, to ścieżka o zerowej długości od q do u wraz z tą krawędzią utworzyłaby ścieżkę o ujemnej długości od q do v , co jest sprzeczne z faktem, że wszystkie wierzchołki mają zerową odległość od q . Brak ujemnych krawędzi zapewnia optymalność ścieżek znalezionych przez algorytm Dijkstry. Odległości na oryginalnym wykresie można obliczyć na podstawie odległości obliczonych przez algorytm Dijkstry na wykresie przeważonym poprzez odwrócenie transformacji ponownego ważenia.

Analiza

Złożoność czasowa tego algorytmu, wykorzystującego stosy Fibonacciego w implementacji algorytmu Dijkstry, wynosi ${\ Displaystyle O (| V | ^ {2} \ log |V|+|V||E|)}$ : algorytm wykorzystuje ${\ Displaystyle O (| V||E|)}$$_$ algorytmu _ ${\ displaystyle | V|}$ instancje algorytmu Dijkstry. Tak więc, gdy wykres jest rzadki , całkowity czas może być szybszy niż algorytm Floyda-Warshalla , który rozwiązuje ten sam problem w czasie ${\ Displaystyle O (| V | ^ {3})}$ .

Linki zewnętrzne

• Wzmocnienie: wszystkie pary najkrótszych ścieżek