Tekst źródłowy strony Algorytm Bellmana-Forda

{{Algorytm infobox
 | nazwa            = 
 | grafika          = 
 | wielkość grafiki = 
 | opis grafiki     = 
 | rodzaj           = [[problem najkrótszej ścieżki]]
 | struktura        = [[graf skierowany]]
 | czas             = <math>O(|V|\cdot|E|)</math>
 | pamięć           = <math>O(|V|)</math>
}}
'''Algorytm Bellmana-Forda''' – algorytm służący do [[problem najkrótszej ścieżki|wyszukiwania najkrótszych ścieżek]] w [[graf (matematyka)|grafie]] ważonym z wierzchołka źródłowego do wszystkich pozostałych [[wierzchołek (teoria grafów)|wierzchołków]]<ref name="wprowadzenie">{{Cytuj książkę | nazwisko = Cormen| imię = Thomas H. | nazwisko2 = Leiserson| imię2 = Charles E. | nazwisko3 = Rivest| imię3 = Ronald L. | nazwisko4 = Stein| imię4 = Clifford | tytuł = Wprowadzenie do algorytmów | wydawca = Wydawnictwo Naukowe PWN | miejsce = Warszawa | rok = 2012 | strony = 664–665 | isbn = 978-83-01-16911-4 }}</ref>.

Idea [[algorytm]]u opiera się na [[metoda relaksacji|metodzie relaksacji]] (dokładniej następuje relaksacja <math>|V|-1</math> razy każdej z [[Krawędź grafu|krawędzi]]).

W odróżnieniu od [[algorytm Dijkstry|algorytmu Dijkstry]], algorytm Bellmana-Forda działa poprawnie także dla grafów z wagami ujemnymi (nie może jednak wystąpić cykl o łącznej ujemnej wadze osiągalny ze źródła). Za tę ogólność płaci się jednak wyższą [[złożoność obliczeniowa|złożonością czasową]]. Działa on w czasie <math>O(|V|\cdot |E|)</math><ref name="wprowadzenie" />.

Algorytm może być wykorzystywany także do sprawdzania, czy w grafie występują ujemne cykle osiągalne ze źródła<ref name="wprowadzenie" />.

Na algorytmie Bellmana-Forda bazuje protokół RIP - [[Routing Information Protocol]]<ref>{{Cytuj stronę | url = http://web.archive.org/web/20170519113335/http://cisco.sadzer.pl/routing/rip/ | tytuł = RIP {{!}} Cisco dla początkujących| opublikowany = cisco.sadzer.pl | praca = | data = | język = | data dostępu = 2017-03-31}}</ref>.

== Zapis w pseudokodzie ==

Dla grafu ''G'', funkcji wagowej ''w'' i wierzchołka ''s'' otrzymamy tablicę ''d''[''u''] odległości każdego wierzchołka grafu od wierzchołka ''s''.

 Bellman-Ford(''G'',''w'',''s''):
 
 '''dla każdego''' wierzchołka v w V[G] '''wykonaj'''
   d[v] = nieskończone
   poprzednik[v] = niezdefiniowane
 d[s] = 0
 '''dla''' i '''od''' 1 '''do''' |V[G]| - 1 '''wykonaj'''
   '''dla każdej''' krawędzi (u,v) w E[G] '''wykonaj'''
     '''jeżeli''' d[v] > d[u] + w(u,v) '''to'''
       d[v] = d[u] + w(u,v)
       poprzednik[v] = u

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* [http://www.algorytm.org/index.php?option=com_content&task=view&id=94&Itemid=28 Opis algorytmu na algorytm.org]
* [http://algorytmy.ency.pl/tutorial/algorytm_bellmana_forda Przykładowe wykonanie algorytmu ''krok po kroku'']

{{Teoria grafów}}

[[Kategoria:Algorytmy grafowe|Bellmana-Forda]]