Bellman–Ford algorithm

The Bellman–Ford algorithm finds shortest paths from one source in a weighted graph, even with negative edge weights, and detects reachable negative-weight cycles.

Edge relaxation: An operation that improves a tentative path estimate by using a known path to a neighboring vertex. Bellman–Ford applies this operation to every edge in repeated passes.
Directed graph: A graph whose edges have specified directions. Bellman–Ford relaxes each directed edge according to its orientation.
Dijkstra's algorithm: A single-source shortest-path algorithm that repeatedly finalizes the nearest unsettled vertex. It is typically faster but requires nonnegative edge weights for correctness.
Currency arbitrage: A trading strategy that exploits exchange-rate inconsistencies to end with more of a currency than it began with. Log-transformed exchange rates turn profitable trading cycles into negative cycles detectable by shortest-path methods.
Richard Bellman: An American mathematician who developed dynamic programming and contributed to control theory and optimization. His work on shortest paths supplied one of the algorithm's namesakes.
Shortest-path problem: The problem of finding minimum-cost paths between specified vertices in a graph. Bellman–Ford solves the single-source version of this broader optimization problem.
Weighted graph: A graph whose edges carry numerical values called weights. Those weights determine the path costs Bellman–Ford compares.
Floyd–Warshall algorithm: A dynamic-programming algorithm that finds shortest paths between every pair of vertices. It handles negative edges but computes all-pairs distances rather than one source's distances.
Difference constraints: Inequalities of the form xᵥ − xᵤ ≤ c represented by weighted directed edges. Bellman–Ford can test whether such constraints are consistent by checking for negative cycles.
Lester R. Ford Jr.: An American mathematician known for work in network flows and combinatorial optimization. His shortest-path work supplied the algorithm's other namesake.

Linked from 4 pages