algorytm.org

Start
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Forda-Bellmana
Ocena użytkowników:***** / 54
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:23

Algorytm ten służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie bez cykli o ujemnej długości.
Warunek nieujemności cyklu jest spowodowany faktem, że w grafie o ujemnych cyklach najmniejsza odległość między niektórymi wierzchołkami jest nieokreślona, ponieważ zależy od liczby przejść w cyklu.
Dla podanego grafu macierz A dla każdej pary wierzchołków u i v zawiera wagę krawędzi (u,v), przy czym jeśli krawędź (u,v) nie istnieje, to przyjmujemy, że jej waga wynosi nieskończoność i wpisujemy *.
Algorytm Forda-Bellmana w każdym kroku oblicza górne oszacowanie D(vi) odległości od wierzchołka s do wszystkich pozostałych wierzchołków vi. W pierwszym kroku przyjmujemy D(vi)=A(s,vi).
Gdy stwierdzimy, że D(v)>D(u)+A(u,v), to każdorazowo polepszamy aktualne oszacowanie i podstawiamy D(v):=D(u)+A(u,v). Algorytm kończy się, gdy żadnego oszacowania nie można już poprawić, macierz D(vi) zawiera najkrótsze odległości od wierzchołka s do wszystkich pozostałych.

Pseudokod wygląda następująco:(n- liczba wierzchołków)

begin;
for v:=[1..n] do D(v):=A(s,v); //przyjmujemy, że najkrótszą drogą z u do v jest krawędź (u,v)
for k:=1 to (n-2) do //w (n-2) krokach można zbadać każdą drogę o (n-1) krawędziach i wybrać najkrótszą
begin
for v:=[1..n]-{s} do //odległość od s do s wynosi 0 i już się na pewno nie zmieni
for u:=[1..n] do
D(v):=min{D(v), D(u)+A(u,v)}; //wybierz krótszą drogę
end;

Algorytm można ulepszyć sprawdzając w każdej iteracji, czy coś się zmieniło od poprzedniej i jeśli nie, to można zakończyć obliczenia.
Dla pełnej jasności podam teraz prosty przykład: oto graf i jego reprezentacja w postaci macierzy wag krawędzi.
Przyjmujemy s=1, symbol "*" oznacza nieskończoność:

ImageImage
Oto przebieg obliczeń:
kD(1)D(2)D(3)D(4)D(5)D(6)
0024***
10242a6b4c
202425d4
3024254
Objaśnienia:
W pierwszym kroku (k=0) D(vi)=A(1,vi). Przepisujemy pierwszy wiersz macierzy wag krawędzi.
a). Pierwsze skrócenie drogi: w poprzednim kroku D(4)=*, gdyż nie istnieje krawędź od 1 do 4. Teraz jednak możemy przejść przez wierzchołek 3 (odległość od 1 do 3 wynosi 4) a następnie do 4 (waga krawędzi [3,4]=-2), długość drogi od 1 do 4 wynosi więc 4-2 = 2.
b). Podobnie jest tu, do wierzchołka 5 możemy dojść przez 2, 3, lub 6. Wybieramy oczywiście drogę o mniejszej długości:
  • D(2)+A(2,5)=2+4=6 (ta wartość jest najmniejsza)
  • D(3)+A(3,5)=4+3=7
  • D(6)+A(6,5)=*+1 (ta wartość jest największa)
Wybieramy opcję z wierzchołkiem nr. 2.
c). Do wierzchołka 6 możemy dojść przez 4 (do którego dochodzimy przez 3) droga jest więc następująca: 1, 3, 4, 6 a jej długość wynosi D(4)+A(4,6)=2+2=4
d). Jak wynika z punktu b), do wierzchołka 5 możemy dojść także poprzez wierzchołek 6. W poprzednim kroku poznaliśmy odległość do wierzchołka 6 i nie wynosi ona już nieskończoność. Sprawdźmy więc, jaka byłaby długość drogi do wierzchołka 5 poprzez 6: D(6)+A(6,5) = 4+1 = 5. Jest to wartość mniejsza niż aktualna (6), więc znaleźliśmy krótszą drogę.
W kroku k=3 nic się nie zmieniło od kroku k=2. Kończymy obliczenia i mamy wektor najkrótszych dróg od wierzchołka s=1 do wszystkich pozostałych.
Złożoność obliczeniowa: O(n3).
Uwaga:
Dla grafów z wagami o nieujemnych wartościach lepiej jest stosować Algorytm Dijkstry.
Po znalezieniu najkrótszej odległości między wierzchołkami możemy znaleźć drogę łączącą te wierzchołki za pomocą algorytmu konstrukcji drogi.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Michał KnasieckiC/C++
.cpp
.cpp
***** / 17
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 3
Tomasz LubińskiJava
.java
.java
***** / 17
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 09 sierpnia 2012 15:18
Komentarze
photo
-1 # emil3566 2012-03-01 21:34
Nie zgodzę się z tą złożonością obliczeniową ! Czyli jaką według Ciebie ma złożoność Floyd ? n^4 ? To właśnie Floyd ma złożoność n^3.

Algorytm Forda-Bermama wykonuje się w czasie O(m(n-1)). Można zapytać , czemu ? Nie bede przytaczac dowodu ,jednak jest właściwośc iż przy każdorazowym sprawdzaniu wieszchołkow i ich krawedzi oraz wartości nie wykonamy tej czynności wiecej niz n-1 razy , wiec wykonujemy (n-1) po m razy, m- ponieważ za każdym razem przeszukujemy wszystkie krawędzie. Ni jak nie wiedzę tu sześcianu !!! Proszę o wyjaśnienie lub konfrontacje zdań :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # Tomasz Lubiński 2012-03-05 10:01
Myślę, że autor po prostu uogólnił liczbę krawędzi, których w grafie może być n*n, czyli m=n*n, co daje n*n*(n-1) co równe jest O(n^3).
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # emil3566 2012-03-05 16:57
Przydałoby się wyjaśnienie , ponieważ graf nieskierowany może już miec tylko n(n-1)/2 krawedzi n^3 zachodzi tylko w grafie skierowanym zakładając pesymistycznie ze wszystkie krawędzi są użyte
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # emil3566 2012-03-01 21:45
W ciągu najbliższych dni postaram się zrobić własny artykuł o Bermanie ponieważ uważam iż nie masz racji i wiele kwestii jest przedstawiony w bardzo nieprzystępny sposób a inne są gorszymi rozwiązanami z tych możliwych
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-10 # aaa 2013-06-29 18:17
Dlaczego w grafie jest krawędź o ujemnej wadze skoro nie możemy stosować tego algorytmu jeśli występują krawędzie o ujemnej wadze?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz