|
gptkbp:instanceOf
|
gptkb:algorithm
Graph algorithm
|
|
gptkbp:alternativeTo
|
gptkb:Dijkstra's_algorithm
|
|
gptkbp:assumes
|
No negative cycles reachable from source
|
|
gptkbp:canBe
|
Routing protocols
|
|
gptkbp:canBeParallelized
|
No
|
|
gptkbp:category
|
Dynamic programming
Shortest path algorithms
|
|
gptkbp:complexity
|
O(VE)
|
|
gptkbp:detects
|
Negative weight cycles
|
|
gptkbp:firstPublished
|
1958
|
|
gptkbp:handles
|
Negative edge weights
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Bellman-Ford Algorithm
|
|
gptkbp:input
|
graph
Source vertex
|
|
gptkbp:lessEfficientThan
|
gptkb:Dijkstra's_algorithm
|
|
gptkbp:namedAfter
|
gptkb:Richard_Bellman
gptkb:Lester_Ford_Jr.
|
|
gptkbp:output
|
Infinity if no path exists
Predecessor information
Shortest path distances
|
|
gptkbp:solvedBy
|
Single-source shortest path problem
|
|
gptkbp:spaceComplexity
|
O(V)
|
|
gptkbp:step
|
Check for negative cycles
Relax all edges V-1 times
|
|
gptkbp:usedIn
|
gptkb:RIP_protocol
Operations research
Network analysis
Distance-vector routing
|
|
gptkbp:worksWith
|
Weighted directed graphs
|
|
gptkbp:bfsParent
|
gptkb:Dynamic_Programming
gptkb:Graph_Algorithms
|
|
gptkbp:bfsLayer
|
6
|