Bellman–Ford algorithm
E880220
The Bellman–Ford algorithm is a graph shortest-path algorithm that can handle negative edge weights and detect negative cycles, often used in routing and network optimization.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
graph algorithm
ⓘ
shortest path algorithm ⓘ single-source shortest path algorithm ⓘ |
| advantageOver | Dijkstra's algorithm with respect to negative weights ⓘ |
| alsoKnownAs | Bellman-Ford-Moore algorithm NERFINISHED ⓘ |
| assumes | no overflow in distance calculations ⓘ |
| basedOn | dynamic programming ⓘ |
| canBeOptimizedBy | early stopping when no updates occur ⓘ |
| canDetect | negative weight cycles reachable from source ⓘ |
| canHandle | negative edge weights ⓘ |
| category |
combinatorial optimization
ⓘ
computer science algorithm ⓘ graph theory ⓘ |
| comparedWith | Dijkstra's algorithm NERFINISHED ⓘ |
| coreOperation | edge relaxation ⓘ |
| detectionMethodForNegativeCycles | extra relaxation pass that finds further distance decreases ⓘ |
| disadvantageComparedTo | Dijkstra's algorithm in time complexity on non-negative graphs ⓘ |
| failsWhen | negative cycle is present and distances are considered finite ⓘ |
| generalizes | shortest paths in presence of negative edges ⓘ |
| input |
graph with edge weights
ⓘ
single source vertex ⓘ |
| namedAfter |
Lester R. Ford Jr.
NERFINISHED
ⓘ
Richard Bellman NERFINISHED ⓘ |
| notSuitableFor | graphs with negative cycles when finite shortest paths are required ⓘ |
| numberOfRelaxationPasses | |V| - 1 GENERATED ⓘ |
| operatesOn |
weighted directed graph
ⓘ
weighted undirected graph ⓘ |
| originalAuthor |
Lester R. Ford Jr.
NERFINISHED
ⓘ
Richard Bellman NERFINISHED ⓘ |
| originallyPublishedIn | 1950s ⓘ |
| output | shortest path distances from source to all vertices ⓘ |
| relatedConcept |
distance-vector algorithm
ⓘ
shortest path problem ⓘ |
| requiresEdgeWeightsToBe | finite ⓘ |
| spaceComplexity | O(V) ⓘ |
| terminationCondition | no distance updated in a full pass or after |V|-1 passes ⓘ |
| timeComplexityTypical | O(V * E) ⓘ |
| timeComplexityWorstCase | O(V * E) ⓘ |
| typicalInitialization |
distance to all other vertices is infinity
ⓘ
distance to source is 0 ⓘ |
| usedAsSubroutineIn | Johnson's algorithm for all-pairs shortest paths ⓘ |
| usedFor | feasibility check of potentials in reweighting schemes ⓘ |
| usedIn |
distance-vector routing
ⓘ
distributed routing algorithms ⓘ dynamic programming teaching ⓘ network optimization ⓘ routing protocols ⓘ |
| worksWith |
directed graphs
ⓘ
undirected graphs modeled as bidirected ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.