relaxation

Checking whether going through vertex u gives a cheaper route to its neighbour v than the best one known, and updating v's distance if so.

In more detail

Relaxing edge (u, v) with weight w sets dist[v] = dist[u] + w when that is smaller. Dijkstra's algorithm relaxes each edge once, in a greedy order; Bellman-Ford relaxes every edge V minus one times, which lets it cope with negative weights.

Related terms

Taught in

References