algorytm Bellmana-Forda

Also known as Bellman–Ford–Moore algorithm, Bellman-Ford equation, distance-vector routing algorithm

algorithm for finding single-source shortest paths in graphs, allowing some edge weights to be negative

Key facts

Class: Single-source shortest path problem (for weighted directed graphs)
Data structure: Graph
Worst case performance: Θ ( | V | | E | ) {\displaystyle \Theta (|V||E|)}
Best case performance: Θ ( | E | ) {\displaystyle \Theta (|E|)}
Worst case space complexity: Θ ( | V | ) {\displaystyle \Theta (|V|)}

via Wikipedia infobox

Wikidata facts

Named after: L. R. Ford, Jr.
Image: Bellman–Ford algorithm example.gif

Show 5 more facts

uses: graph data structure
discoverer or inventor: Edward F. Moore
derivative work: Babel
Commons category: Bellman–Ford algorithm
used by: distance-vector routing protocol

Sources (2)

via Wikidata · CC0

Article · Polski

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. 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 . Algorytm może być wykorzystywany także do sprawdzania, czy w grafie występują ujemne cykle osiągalne ze źródła. Na algorytmie Bellmana-Forda bazuje protokół RIP - Routing Information Protocol.

Abstract from DBpedia / Wikipedia · CC BY-SA

Available in 29 languages

Show 10 more

via Wikidata sitelinks · CC0