Algorytmy, struktury danych i techniki programowania. Wydanie V
49,00 zł
Zrozum struktury danych. Algorytmy i praca na danych w Javie
−30%27,93 zł
Opus magnum C++11. Programowanie w języku C++ (komplet)
149,00 zł
Kwalifikacja EE.08. Montaż i eksploatacja systemów komputerowych, urządzeń peryferyjnych i sieci. Część 2. Systemy operacyjne. Podręcznik do nauki zawodu technik informatyk
37,95 zł
Kwalifikacja E.12. Montaż i eksploatacja komputerów osobistych oraz urządzeń peryferyjnych. Podręcznik do nauki zawodu technik informatyk
57,00 zł
Kwalifikacja E.14. Część 3. Tworzenie aplikacji internetowych. Podręcznik do nauki zawodu technik informatyk
37,95 zł

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!

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

  1. A. Debudaj-Grabysz, S. Deorowicz, J. Widuch, Algorytmy i struktury danych. Wybór zaawansowanych metod, Wydawnictwo Politechniki Śląskiej, Gliwice, 2012
Ocena: 0 Tak Nie
Liczba głosów: 0.

Dodano: 30 marca 2017 19:25, ostatnia edycja: 12 sierpnia 2017 13:52.

Zobacz też

Wyznaczanie najkrótszej ścieżki – zagadnienie polegające na wyszkaniu w grafie takiej ścieżki łączącej dwa wierzchołki, której suma wag krawędzi jest jak najmniejsza.

W przypadku pesymistycznym do wyznaczenia optymalnej ścieżki z wierzchołka A do wierzchołka B konieczne jest wyznaczenie najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych wierzchołków w grafie. Zagadnienie takie jest określane jako poszukiwanie najkrótszych ścieżek z jednego źródła. Do rozwiązywania tego zagadnienia można wykorzystać następujące algorytmy:

Nieco innym zagadnieniem jest poszukiwanie najkrótszych ścieżek pomiędzy każdą parą wierzchołków. W tym celu można wykorzystać algorytmy wymienione powyżej (wykonując je wielokrotnie, za każdym razem przyjmując inny wierzchołek źródłowy) lub algorytmy poszukujące od razu wszystkich ścieżek, takie jak:

Aby znalezienie najkrótszej ścieżki było możliwe, graf nie może zawierać ujemnych cykli osiągalnych z wierzchołka źródłowego. Jeśli taki cykl istnieje, to poruszając się nim „w kółko” cały czas zmniejszamy długość ścieżki. Dopuszczalne jest natomiast występowanie krawędzi o ujemnej wadze, choć nie wszystkie algorytmy dopuszczają ten przypadek.

Jeśli poszukujemy ścieżek o najmniejszej liczbie krawędzi (np. wtedy, gdy wszystkie krawędzie mają taką samą, dodatnią wagę), to zamiast powyższych algorytmów możemy skorzystać z prostego przeszukiwania grafu wszerz.

→ Czytaj całość
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
→ Czytaj całość

Algorytm – przepis, zbiór poleceń, opis ciągu operacji prowadzących do rozwiązania konkretnego problemu. Algorytm możemy również rozumieć jako funkcję przekształcającą dane wejściowe w dane wyjściowe.

Algorytm musi być skończony, czyli jego zapis ma składać się ze skończonej liczby znaków. Musi również być poprawny, czyli dla wszystkich możliwych danych wejściowych powinien zwracać prawidłowy wynik (może być nim informacja o braku rozwiązania). Algorytm musi wykazywać również własność stopu – niezależnie od danych wejściowych obliczenia algorytmu powinny dochodzić do punktu końcowego, czyli po prostu kończyć się (nie mogą np. wpadać w nieskończoną iterację). Zapis algorytmu musi być precyzyjny, bez jakichkolwiek niejasności.

→ Czytaj całość
Polityka prywatnościKontakt