DiffPush Tier Graphs · Shortest Path Problems O(V * E) · O(V)
A settlement grid routes money between accounts over channels that may carry rebates — negative costs. The finance desk must know each account's cheapest receivable total from the clearing house, but a loop of rebates that keeps shrinking its own payout poisons the books. Bellman-Ford answers both: the cheapest totals, or a hard alarm if such a rebate loop exists.
Input: An integer V (vertices 0..V-1), an edge list edges where [u, v, w] is a one-way channel u -> v with cost w (possibly negative), and the source S.
Output: Return the array of shortest distances from S, or the single-element array [-1] if a negative cycle is reachable from S.
1 <= V <= 10^31 <= edges.length <= 5 * 10^3-10^3 <= w <= 10^30 <= S < VInput: {"V":3,"S":2,"edges":[[0,1,5],[1,0,3],[1,2,-1],[2,0,1]]}
Output: [1,6,0]
Node 0 is reached by 2 -> 0 costing 1; node 1 rides through 0 for 6.
Input: {"V":2,"S":0,"edges":[[0,1,4]]}
Output: [0,4]
A single channel settles both accounts immediately.