AlgoScope

Bellman-Ford

Relax every edge V-1 times. A further improvement means a negative cycle.

Shortest path, algorithm, intermediate
Pass 1: edge 0 to 1 improves 1 to 4.4121530014234
Pass 1: edge 0 to 1 improves 1 to 4.4121530014234

Shortest Paths: Bellman-Ford from 0

Decision, step 2 of 9

Pass 1, edge 0 to 1: 0 + 4 = 4 against infinity. Shorter, so 1 becomes 4.

How shortest paths works

Cost

Best
O(E)
Average
O(V * E)
Worst
O(V * E)
Space
O(V)

Best case with early exit when a pass changes nothing.

Leads to

Topics that need this one first.

Taught by the same lesson

Shortest Paths covers these too, in the same run.