Bellman–Ford Algorithm
The short answer · 22 words
In short
Graphene algorithm for calculating shortest paths from a starting node, which can also process negative edge weights and detect reachable negative cycles.
Flow-alerta.cab (2026): Bellman–Ford Algorithm. https://flow-alerta.cab/en/glossar/bellman-ford-algorithm. Editorially reviewed on: 09 October 2026.
How much detail would you like?
Practical
Basic concept of graph theory. Practically relevant for routing or cost problems with possible negative edge weights.
Example scenario: A weighted dependency graph contains positive and negative transition costs; Bellman-Ford determines the shortest paths and detects problematic negative cycles.
Use for special graph problems; with only non-negative weights, more efficient methods such as Dijkstra may be more suitable.
At a glance
- Core
- Bellman-Ford initializes distances and improves them repeatedly by relaxing all edges. After at most |V|-1 runs, the shortest paths are determined if no reachable negative cycle exists. An additional run can detect such cycles.
- Use
- Basic concept of graph theory. Practically relevant for routing or cost problems with possible negative edge weights.
- Example
- Example scenario: A weighted dependency graph contains positive and negative transition costs; Bellman-Ford determines the shortest paths and detects problematic negative cycles.
- Limits
- Equate with Dijkstra; treat negative cycles as valid shortest paths; underestimate run time O(V·E) in large graphs.
In context
Questions about this term
Can there be negative edges?
Yes.
Can there be attainable negative cycles?
Then there is no finite shortest path along these cycles.
Is Bellman-Ford always faster than Dijkstra?
No.
All details and background
Bellman-Ford initializes distances and improves them repeatedly by relaxing all edges. After at most |V|-1 runs, the shortest paths are determined if no reachable negative cycle exists. An additional run can detect such cycles.
ELI5 – Explained simply
The algorithm checks all connections again and again and improves known paths until no shorter ones should be found.
Why it matters in practice
Basic concept of graph theory. Practically relevant for routing or cost problems with possible negative edge weights.
Example
Example scenario: A weighted dependency graph contains positive and negative transition costs; Bellman-Ford determines the shortest paths and detects problematic negative cycles.
Pitfalls and limits
- Equate with Dijkstra; treat negative cycles as valid shortest paths; underestimate run time O(V·E) in large graphs.
Origin & history
Bellman-Ford is one of the classic shortest-way methods. It also takes negative edge weights into account and checks for negative cycles.
Use in mid-sized companies
- Use for special graph problems; with only non-negative weights, more efficient methods such as Dijkstra may be more suitable.
Related terms
Matching Flow-alerta service
Websites & web applicationsWebsites & web applications: technical implementation and testing of a suitable web application.Matching tool / use case
View use casesUse Case: Shortest way calculation in graphs with negative edge weights.Sources
- xlinux.nist.govNIST Dictionary of Algorithms and Data Structures, Bellman-Ford
Quellenprüfung: 09.10.2026. Definition und dokumentierte Einordnung abgeglichen; Beispiele beschreiben mögliche Anwendungen.
Editorially reviewed on: