The Bellman-Ford algorithm solves the single source [[shortest path]] problem. For a specified source node, the algorithm constructs a table with destination, cost, and parent. The cost is initialized for every destination (except the source) as $\infty$. Using a method called `relax`, a valid path cost is calculated for each edge. Iterate over the graph $n-1$ times where $n$ is the number of vertices, relaxing each time. For two nodes `u` and `v`, the method `relax(u,v)` sums the current cost assigned to node `u` and the cost of the edge from `u` to `v`. If this total is less than the cost currently assigned to node `v`, the cost at node `v` is updated with this new cost. If the cost is updated, also update the parent for `v` to be `u`. $n-1$ iterations are needed in the worst case, which is a straight-line graph where iterations start from the tail. Finally, check for a negative weight cycle by iterating one last time. If one or more edges can be further relaxed, there must be a negative weight cycle. In this case, the shortest path solution is undefined. If the graph is a directed acyclic graph (DAG), first sort the graph topologically and then run Bellman-Ford with only one iteration through each node in this order.