![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Bellman%25E2%2580%2593Ford_algorithm_example.gif/640px-Bellman%25E2%2580%2593Ford_algorithm_example.gif&w=640&q=50)
Algorytm Bellmana-Forda
Z Wikipedii, wolnej encyclopedia
Algorytm Bellmana-Forda – algorytm służący do wyszukiwania najkrótszych ścieżek w grafie ważonym z wierzchołka źródłowego do wszystkich pozostałych wierzchołków[1].
Szybkie fakty Rodzaj, Struktura danych ...
![]() | |
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Pamięciowa |
|
Zamknij
Idea algorytmu opiera się na metodzie relaksacji (dokładniej następuje relaksacja razy każdej z krawędzi).
W odróżnieniu od 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ścią czasową. Działa on w czasie [1].
Algorytm może być wykorzystywany także do sprawdzania, czy w grafie występują ujemne cykle osiągalne ze źródła[1].
Na algorytmie Bellmana-Forda bazuje protokół RIP - Routing Information Protocol[2].