Bellman-Ford Algorithm

Context:
- It can handle Negative Edge-Eight Graphs.
- …
Example(s):
- as proposed in (Busato & Bombieri, 2015).
- as proposed in (Goldberg & Radzik, 1993).
- …
Counter-Example(s):
- Dijkstra's Algorithm, which is typically faster but can't handle negative edge weights.
See: Dynamic Programming Algorithm, Graph Theory, Shortest Path Problem, Dijkstra's Algorithm.

References

(Wikipedia, 2023) ⇒ https://en.wikipedia.org/wiki/Bellman-Ford_Algorithm Retrieved:2023-10-25.
- Bellman–Ford algorithm is an algorithm for finding the shortest paths from a single source vertex to all the other vertices in a weighted directed graph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

(Weber et al., 2020) ⇒ A Weber, M Kreuzer, and A Knoll. (2020). "A generalized Bellman-Ford algorithm for application in symbolic optimal control." In: 2020 European Control Conference (ECC).
- QUOTE:… allows for efficient implementation by parallelizing both the execution of the algorithm itself … Bellman-Ford algorithm [12]–[14] for directed hypergraphs. The Bellman-Ford algorithm (on …
- NOTE: It presents a generalized version of the Bellman-Ford Algorithm adapted for symbolic optimal control applications.

(Busato & Bombieri, 2015) ⇒ F. Busato, and N. Bombieri. (2015). "An Efficient Implementation of the Bellman-Ford algorithm for Kepler GPU Architectures." IEEE Transactions on Parallel and Distributed Systems. DOI:7121663
- QUOTE: "… The Bellman-Ford’s algorithm is the solution that solves such a single-source shortest path … This article presents a parallel implementation of the Bellman-Ford algorithm that exploits … "
- NOTE: It illustrates the adaptation of the Bellman-Ford Algorithm for efficient execution on GPU architecturees.

(Bannister & Eppstein, 2012) ⇒ M.J. Bannister, and D. Eppstein. (2012). "Randomized Speedup of the Bellman–Ford Algorithm." In: Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments. SIAM.
- QUOTE: "… We describe a variant of the Bellman–Ford algorithm for single-source shortest paths in graphs with negative edges but no negative cycles that randomly permutes the vertices and uses …"
- NOTE: It introduces a Bellman-Ford Algorithm variant optimized for graphs with negative edges but without any negative cycles.

(Goldberg & Radzik, 1993) ⇒ A.V. Goldberg, and T. Radzik. (1993). "A Heuristic Improvement of the Bellman-Ford Algorithm." CiteSeer.
- QUOTE:" … We describe a new shortest paths algorithm. Our algorithm achieves the same O(nm) worst-case time bound as Bellman-Ford algorithm but is superior in practice. … In practice …
- NOTE: It presents an improved variant of Bellman-Ford Algorithm that demonstrates better performance in practical scenarios.