Bellman-Ford Algorithm is a dynamic programming problem that solves single-source shortest path. d[v] = \infty d[s] = 0 for i = 0, ..., n-2: for v in v: d_prev = d for u in v.in_neigbors: d[v] = min(d_prev[v], d_prev[u] + w(u,v)) Notice you need O\left(n\right) space (2 d rounds, the previous round and the next round), and runtime is O\left(nm\right) (outer n loop, inner is an iteration between deg\left(v\right)*|v| = |e| = m; that is, we have an minimum over the degree of each v for every v, which adds up to the total number of edges.) d^{(i)}[v] is the cost of the shortest path between s and v with at most i edges (i.e. we propagate “one edge of minimum” forward each time). So d^{(n-1)}[v] is the cost of the shortest path between s and v if there are no negative cycles. if there are no negative cycle, after n iterations, the distance estimates will stop changing if there is a negative cycle, then the distances will keep updating …so you can just run one more iteration of Bellman-Ford Algorithm to check for negative cycles.