Algorytm Bellmana-Forda

Tutorial
Na ten temat mamy również tutorial „Algorytm Bellmana-Forda”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!
REKLAMA

Czysty kod. Podręcznik dobrego programisty
−30%48,30 zł
Thinking in Java. Edycja polska. Wydanie IV
149,00 zł

Algorytm Bellmana-Forda – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. W odróżnieniu od algorytmu Dijkstry, algorytm Bellmana-Forda dopuszcza krawędzie o ujemnych wagach, nie mogą istnieć jednak ujemne cykle osiągalne z wierzchołka źródłowego. Algorytm może być również wykorzystywany do sprawdzania, czy w grafie występują ujemne cykle.

Algorytm występuje również pod nazwą algorytm Bellmana-Forda-Moore’a.

Opis działania algorytmu

W trakcie wykonywania algorytmu dla każdego wierzchołka zostają wyznaczone dwie wartości: koszt dotarcia do tego wierzchołka (oznaczmy go jako di) oraz poprzedni wierzchołek na ścieżce (oznaczmy go jako pi). Na początku działania algorytmu dla wierzchołka źródłowego koszt dotarcia wynosi 0 (już tam jesteśmy), a dla każdego innego wierzchołka nieskończoność (w ogóle nie wiemy, jak się tam dostać).

Następnie dla każdej krawędzi (oznaczmy, że aktualnie analizowana krawędź ma wagę k i prowadzi z wierzchołka u do wierzchołka v) wykonujemy następującą czynność:

Jeżeli dv > du + k, to ustawiamy wartość dv na du + k, a wartość pv na u.

Całość (przejrzenie wszystkich krawędzi) należy powtórzyć n-1 razy, gdzie n jest liczbą wierzchołków. W każdej iteracji należy przejrzeć wszystkie krawędzie w tej samej kolejności. Jeśli w którejś iteracji nie nastąpią żadne zmiany, wykonywanie algorytmu można przerwać wcześniej.

Wykrywanie ujemnych cykli

Po zakończeniu działania algorytmu, dla każdej krawędzi powinna być spełniona nierówność: dvdu + k (k to waga krawędzi, krawędź prowadzi z wierzchołka u do v). Mówiąc inaczej, kolejna iteracja algorytmu nie powinna spowodować jakichkolwiek zmian. Jeśli ten warunek nie jest spełniony, to w grafie występuje ujemny cykl osiągalny z wierzchołka źródłowego.

Aby sprawdzić występowanie ujemnych pętli w całym grafie, należy dodać do grafu nowy wierzchołek, połączyć go krawędziami o zerowej wadze ze wszystkimi innymi wierzchołkami, a następnie wykonać algorytm traktując ten nowy wierzchołek jako wierzchołek źródłowy. Można również po prostu wykonać algorytm n razy (za każdym razem dla innego wierzchołka źródłowego), jednak zwiększyłoby to złożoność obliczeniową.

Złożoność czasowa

Dla grafu liczącego n wierzchołków i e krawędzi złożoność pesymistyczna jest równa O(en). Biorąc pod uwagę, że w przypadku braku krawędzi wielokrotnych liczba krawędzi jest zawsze mniejsza od n2, można powiedzieć, że złożoność czasowa algorytmu to O(n3).

Bibliografia

  • Z.J. Czech, S. Deorowicz, P. Fabian, Algorytmy i struktury danych. Wybrane zagadnienia, Wydawnictwo Politechniki Śląskiej, Gliwice, 2010, ISBN 9788373356689.
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 30 marca 2017 19:25, ostatnia edycja: 30 stycznia 2019 15:38.

REKLAMA

Zobacz też

Algorytm Zhanga-Suena – algorytm służący do szkieletyzacji obrazu binarnego. Szkieletyzacja polega na wyborze z obrazu binarnego tych pikseli, które są równo odległe od krawędzi obiektu.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Bogosort – bardzo słaby algorytm sortowania oparty na metodzie prób i błędów. Polega na ustawianiu elementów w losowej kolejności i sprawdzaniu, czy są posortowane. Średnia złożoność tego algorytmu jest rzędu silnia, a w przypadku pesymistycznym algorytm będzie działał w nieskończoność.

Algorytm występuje też w nieco ulepszonej wersji, w której nie sprawdza się wielokrotnie tego samego ustawienia. Wówczas algorytm daje gwarancję znalezienia rozwiązania, jednak jego złożoność czasowa nadal jest rzędu silnia (w przypadku pesymistycznym trzeba sprawdzić wszystkie permutacje zbioru).

Ze względu na bardzo dużą złożoność czasową bogosort nie nadaje się do praktycznych zastosowań. Istnieją proste w implementacji, a znacznie wydajniejsze algorytmy sortujące, np. sortowanie przez wstawianie.

→ Czytaj całość
Polityka prywatnościKontakt