Od inżyniera do menedżera. Tajniki lidera zespołów technicznych
−30%41,30 zł
Algorytmy. Ilustrowany przewodnik
54,90 zł
Unix i Linux. Przewodnik administratora systemów. Wydanie V
179,00 zł
Linux. Profesjonalne administrowanie systemem. Wydanie II
149,00 zł
Praktyka czyni mistrza. Wzorce, inspiracje i praktyki rzemieślników programowania
39,90 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ż

2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.

Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.

→ Czytaj całość

Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.

Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.

→ Czytaj całość

K-opt, algorytm k-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Algorytm ten nie służy do samego wyznaczania trasy, a jedynie do ulepszania jej. Najprostszą wersją tego algorytmu jest algorytm 2-optymalny.

→ Czytaj całość
Polityka prywatnościKontakt