Bellman-Ford Algorytm-Wikipedia

L ‘ Algorytm Bellman-Ford , nazywane również Bellman – Ford – Algorytm Moore ^{[[[ 3 ]} , jest algorytmem, który oblicza najkrótsze ścieżki z danego szczytu źródłowego na ważonym wykresie zorientowanym. Nosi nazwę swoich wynalazców Richard Bellman i Lester Randolph Ford Junior (publikacje w 1956 i 1958 r.) Oraz Edwarda Forresta Moore’a, który odkrył go na nowo w 1959 roku.

W przeciwieństwie do algorytmu Dijkstra, algorytm Bellmana-Ford zezwala na obecność niektórych negatywnych łuków wagowych i umożliwia wykrycie istnienia obwodu chłonnego, to znaczy o ściśle ujemnej całkowitej wadze, dostępnej ze szczytu źródłowego.

Złożoność algorytmu jest w

${DisplayStyle o (| s || a |)}$

Lub

${DisplayStyle | s |}$

to liczba szczytów

${displayStyle | a |}$

to liczba łuków.

Oblicza się algorytm Bellman-Ford, biorąc pod uwagę wykres

${DisplayStyle g = (s, a)}$

Bez ujemnego cyklu masy i szczytu źródłowego

${DisplayStyle sin s}$

, krótsza ścieżka

${DisplayStyle s}$

Na każdym szczycie

${DisplayStyle g}$

. Pozwala także takiej ścieżki na znalezienie poprzedników każdego szczytu na takiej ścieżce. Ponadto umożliwia wykrycie przypadków, w których występuje ujemny cykl masy, a zatem, w których niekoniecznie jest krótszy między dwoma szczytami.

Algorytm wykorzystuje zasadę dynamicznego programowania (jest on traktowany w rozdziale na temat programowania dynamicznego w niektórych książkach algorytmicznych ^{[[[ 4 ]} ). Sub-problublicms to:

• 
  ${DisplayStyle d [t, k]}$

  jest odległością od źródła S do T do T ze ścieżką zawierającą co najwięcej K łuków.

Na :

• 
  ${DisplayStyle d [t, 0] =+infty}$

  Dla

  ${DisplayStyle tneq s}$

  I

  ${DisplayStyle d [s, 0] = 0}$

  ;

• 
  ${DisplayStyle d [t, k] = minleft [d [t, k-1], min _ {{text {arc}} (u, t)} (d [u, k-1]+poids (u, t) )Prawidłowy]}$

  .

Algorytm oblicza wartości

${DisplayStyle d [t, k]}$

według wartości wzrostu k. Odległość od S do T jest

${DisplayStyle d [t, | s | -1]}$

.

Algorytm Bellman-Ford jest zatem pisany przy użyciu danej relacji nawrotów bezpośrednio w poprzednim rozdziale ^{[[[ 5 ]} .

 funkcjonować Bellman-Ford (G = (S, A), Poids, S) Dla W W S DO ZROBIENIA |. d [u] = +∞
   |. pred [u] = null
   d [s] = 0
   // Główna pętla  Dla k = 1 dopóki Rozmiar (y) - 1 DO ZROBIENIA |. dla każdego Arc (u, v) wykresu DO ZROBIENIA |. |. I d [u] + poids (u, v) WIĘC |. |. |. d [v]: = d [u] + poids (u, v)
    |. |. |. pred [v]: = u powrót D, wcześniej 

Pod koniec wykonania tego algorytmu,

${DisplayStyle d [u]}$

reprezentuje długość krótszej ścieżki

${DisplayStyle s}$

ma

${displayStyle u}$

W

${DisplayStyle g}$

, chwila

${DisplayStyle Pred [u]}$

reprezentuje poprzednik

${displayStyle u}$

na krótszej ścieżce

${DisplayStyle s}$

ma

${displayStyle u}$

. Wartość zerowa oznacza, że ​​nie przypisano jeszcze poprzednika

${DisplayStyle Pred [u]}$

.

Algorytm Bellman-Ford jest poprawny tylko na wykresie bez ujemnego cyklu masy. Możemy wykryć obecność takiego cyklu (pod warunkiem, że jest on dostępny ze szczytu

${DisplayStyle s}$

) W następujący sposób: Istnieje ujemny cykl masy wtedy i tylko wtedy, gdy nowa runda pętli zmniejszy się odległość. Tak więc na końcu algorytmu robimy:

 dla każdego Arc (u, v) wykresu DO ZROBIENIA |. I D [v]> d [u] + poids (u, v) WIĘC |. Pokaż „Istnieje cykl chłonny” 

Złożoność algorytmu jest w

${DisplayStyle o (| s || a |)}$

Lub

${DisplayStyle | s |}$

to liczba szczytów i

${displayStyle | a |}$

to liczba łuków. Odpowiada to złożoności w

${DisplayStyle o (| s |^{3})}$

Dla prostego gęstego wykresu ^{[[[ 5 ]} .

Demonstrację korekcji algorytmu można wykonać przez nawrót:

Lemme. Po

${DisplayStyle i}$

Próby głównej pętli:

Dowód. W sprawie

${DisplayStyle i = 0}$

, odpowiadający pierwszemu wykonaniu pętli Do , z jednej strony,

${DisplayStyle d [s] = 0}$

I na każdy szczyt

${DisplayStyle Uneq s}$

W

${DisplayStyle d [u] =+infty}$

, udowodnienie pierwszego punktu, a z drugiej strony,

${DisplayStyle s}$

jest jedynym szczytem, ​​ponieważ jest ścieżka co najwyżej 0 krawędzi łączącego ją

${DisplayStyle s}$

.

W sprawie

${DisplayStyle i}$

Nie nikogo:

• Z jednej strony, załóżmy
  ${DisplayStyle d [v]}$

  być aktualizowane

  ${DisplayStyle d [v]: = d [u]+{text {poids}} (u, v)}$

  . Następnie jako

  ${DisplayStyle d [u] neq +infty}$

  (Ponieważ w przeciwnym razie aktualizacja nie miałaby miejsca),

  ${DisplayStyle d [u]}$

  reprezentuje ciężar ścieżki

  ${DisplayStyle s}$

  ma

  ${displayStyle u}$

  . Dlatego przez budowę,

  ${DisplayStyle d [v]}$

  to waga ścieżki

  ${DisplayStyle s}$

  ma

  ${DisplayStyle v}$

  ;

• Z drugiej strony lub
  ${DisplayStyle C}$

  , krótsza ścieżka

  ${DisplayStyle s}$

  ma

  ${DisplayStyle v}$

  Od najbardziej

  ${DisplayStyle i}$

  kości. Albo

  ${displayStyle u}$

  Ostatni szczyt wcześniej

  ${DisplayStyle v}$

  na tej ścieżce. Albo

  ${DisplayStyle C ‘}$

  , Sideland of

  ${DisplayStyle C}$

  z

  ${DisplayStyle s}$

  ma

  ${displayStyle u}$

  . Następnie przez indukcję,

  ${DisplayStyle C ‘}$

  jest krótszą ścieżką

  ${DisplayStyle s}$

  ma

  ${displayStyle u}$

  Od najbardziej

  ${DisplayStyle I-1}$

  krawędzie (w rzeczywistości, jeśli nie, istnieje ściśle krótsza ścieżka

  ${DisplayStyle s}$

  ma

  ${displayStyle u}$

  . Dodając krawędź

  ${displayStyle u}$

  ma

  ${DisplayStyle v}$

  , istnieje ścieżka ściśle niższa niż

  ${DisplayStyle C}$

  z

  ${DisplayStyle s}$

  ma

  ${DisplayStyle v}$

  , co jest sprzeczne z definicją

  ${DisplayStyle C}$

  ). Następnie, przez hipotezę nawrotów, po iteracji

  ${DisplayStyle I-1}$

  W

  ${DisplayStyle d [u]}$

  był co najwyżej długości krótszej ścieżki

  ${DisplayStyle s}$

  ma

  ${displayStyle u}$

  Od najbardziej

  ${DisplayStyle I-1}$

  kości. Tak więc w

  ${DisplayStyle i}$

  -Me iteracja,

  ${DisplayStyle d [v] leq d [u]+{text {poids}} (u, v)}$

  , ze względu na strukturę algorytmu. Jednak ta ostatnia długość jest co najwyżej długości krótszej ścieżki

  ${DisplayStyle s}$

  ma

  ${DisplayStyle v}$

  .

Dlatego wykazano lemat. Wynika z tego, że długość

${DisplayStyle d [u]}$

jest długością krótszej ścieżki

${DisplayStyle s}$

ma

${displayStyle u}$

, co dowodzi korekcją algorytmu Bellman-Ford w przypadku tego

${DisplayStyle g}$

nie ma ujemnego cyklu masy ^{[[[ 5 ]} .

Wykonanie głównej pętli można zatrzymać, gdy odległości pozostaną niezmienione. Ciało głównej pętli jest następnie wykonywane mniej niż

${DisplayStyle | s | -1}$

czasy. Złożoność w najgorszym przypadku jest niezmieniona. Jen ^{[[[ 6 ]} opisał dwie ulepszenia algorytmu Bellman-Ford, które nie zmieniają złożoności w najgorszym przypadku, ale co sprawia, że ​​jest szybszy w praktyce.

1. Pierwsza poprawa zmniejsza liczbę relaksu. Jeśli d [u] nie został zmodyfikowany od czasu relaksacji łuku (u, t), nie ma potrzeby uwalniania łuków (u, t) po raz drugi. Zatem, wraz ze wzrostem liczby szczytów o prawidłowej odległości podczas algorytmu, liczba łuków, które zostaną uwolnione z każdej iteracji. Zarabiamy stałą czynnik złożoności gęstych wykresów.
2. Drugim ulepszeniem Yena jest wybranie dowolnego całkowitego zamówienia I _F zawiera łuki (u, t) z u I _B , zawiera łuki (u, t) z u> t. Pętla dla każdego ARC (u, t) wykresu DO ZROBIENIA jest przeprowadzany w następujący sposób. Każdy szczyt u jest odwiedzany w kolejności rosnącej <. Następnie uwalniamy każdy łuk (u, t) w I _F . Następnie odwiedzamy szczyty U w zmniejszającej się kolejności>. Uwalniamy łuki (u, t) w I _B . Każda iteracja głównej pętli (z wyjątkiem pierwszej) dodaje co najmniej dwa łuki, których szczyty mają prawidłowe odległości, jeden w I _F i jeden I _B . Ta poprawa zmniejsza liczbę iteracji głównej pętli
   ${DisplayStyle | s | -1}$

   ma

   ${DisplayStyle {frac {| s |} {2}}}$

   .

Kolejna poprawa Banister & Eppstein ^{[[[ 7 ]} polega na zastąpieniu całkowitego zamówienia na szczytach drugiej poprawy jena z losową permutacją. Zatem najgorszy przypadek poprawy jena zdarza się nie często (fakt, że łuki krótszej ścieżki są czasami w I _F czasami w I _B ). Przy losowej permutacji jako całkowitym zamówieniu, nadzieja na liczbę iteracji głównej pętli jest co najwyżej

${DisplayStyle {frac {| s |} {3}}}$

.

W 1993 r. Bahar i in. podano wdrożenie algorytmu Bellman-Ford dla wykresów reprezentowanych symbolicznie za pomocą struktury danych o nazwie algebraicznych diagramów decyzyjnych (ADD), która jest uogólnieniem binarnych diagramów decyzyjnych ^{[[[ 8 ]} .

W sieciach komputerowych algorytm Bellman-Ford służy do określenia ścieżki wiadomości, poprzez protokół routingu RIP ^{[[[ 9 ]} . Możemy użyć algorytmu Bellman-Ford do rozwiązania problemu programowania liniowego, w którym ograniczenia są różnicami. Na przykład : X – I ≤ 5, I – T ≤ 10 itp. Mówiąc dokładniej, taki system ma rozwiązanie, jeśli i tylko wtedy, gdy powiązany wykres nie ma ujemnych cykli masy ^{[[[ dziesięć ] W [[[ 5 ]} .

Oryginalne źródła [[[ modyfikator |. Modyfikator i kod ]

• (W) Richard Herold W ‘ Na temat problemu routingu » W Kwartalnik matematyki stosowanej W tom. 16, 1958 W P. 87–90 (Recenzje matematyczne 0102435 )
• (W) Lester R. Ford Jr. W Teoria przepływu sieci , Santa Monica, Kalifornia, Rand Corporation, coll. «Papier p-923», 14 sierpnia 1956 ( Czytaj online )
• (W) Edward F. Moore (1959). «Najkrótsza ścieżka przez labirynt» Dans Proc. Internat. Sympos. Teoria przełączania 1957, część II : 285–292 s., Cambridge, Mass.: Harvard Univ. Naciskać.
• (W) Jin Y. Jeśli W ‘ Algorytm znajdowania najkrótszych tras ze wszystkich węzłów źródłowych do danego miejsca docelowego w sieciach ogólnych » W Kwartalnik matematyki stosowanej W tom. 27, 1970 W P. 526–530 (Recenzje matematyczne 0253822 )
• (W) M. J. Banister i D. Eppstein (2012) ” Randomizowany przyspieszenie algorytmu Bellman -Ford »(Pdf) w Algorytmiki analityczne i kombinatoryczne (analco12), Kioto, Japonia : 41–47 p ..

Książki po francusku [[[ modyfikator |. Modyfikator i kod ]

• Michel Gondra i Michel Minoux W Wykresy i algorytmy , Eyrolles Editions, coll. „Badania i badania energii elektrycznej z Francji”, 1979 ( ROMPR. 1984, 1995, 2009 Chez Lavoisier, 4e ed.), 548 P. , „2 – najkrótszy problem”