edge relaxation

Every shortest-path algorithm keeps a rough guess of how far each vertex is from the source, and patiently improves those guesses. Edge relaxation is the single tiny move that does the improving. You look at one edge from u to v and ask: 'If I travel to u and then take this edge, is that cheaper than my current best guess for reaching v?' If yes, you lower your guess for v. That is the whole operation — one comparison and maybe one update.

Keep an array d, where d[v] is the current tentative distance from the source to v, started at d[source] = 0 and d[v] = infinity for everyone else. To relax the edge (u, v) with weight w: if d[u] + w < d[v], then set d[v] = d[u] + w (and record u as v's predecessor, so you can recover the route later). Crucially, d[v] is always an over-estimate — it is the cost of some actual known path to v, never less than the true shortest distance — and relaxation can only lower it, never raise it. Different algorithms differ only in the ORDER in which they relax edges and when they stop; the relax step itself is identical in all of them. For example, with d[u] = 5 and an edge of weight 2 to v where d[v] is currently 9, relaxing sets d[v] = 7.

This one operation is the atom from which Dijkstra, Bellman-Ford, and DAG shortest paths are all built. The art of each algorithm is choosing a relaxation order that needs as few relaxations as possible: Dijkstra relaxes each edge once by always finalizing the closest unfinished vertex; Bellman-Ford bluntly relaxes every edge V-1 times. A relaxation never makes any d[v] wrong, so doing extra relaxations is wasteful but never incorrect — the only thing that matters for correctness is that every edge on a true shortest path eventually gets relaxed in the right order.