A single-source shortest-path algorithm that repeatedly relaxes every edge in a graph, slower than Dijkstra's algorithm but able to handle negative edge weights and to detect a negative-weight cycle when one exists.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Classification
Design Technique Credited ToRichard Bellman and Lester Ford Jr. 2 Connections
Credited To
Source Wikipedia, Bellman-Ford algorithm
Source Wikipedia, Bellman-Ford algorithm
In Field
Source Wikipedia, Bellman-Ford algorithm
Invented By
L. R. Ford Jr. published the shortest-path algorithm in a 1956 RAND report that Richard Bellman independently formulated in 1958, giving the algorithm its joint name.
Uses Design Technique
Sources
1. Bellman-Ford Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomial
polynomial
Wikipedia: design technique dynamic-programming
dynamic-programming
View the Source2. Wikipedia, Bellman-Ford algorithm
Lead section
The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.
In Field: Algorithms and Complexity Theory, Lead sentence
Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.
View the SourceWikidata: Bellman-Ford Algorithm
Wikidata Q816022, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.