the triangle-inequality property of shortest paths

There is a common-sense fact about cheapest routes: a detour can never be a bargain. If the cheapest way from the source to a city v costs some amount, then going to a neighbor u first and then taking the road from u to v can never cost LESS than that cheapest amount — at best it ties. Stopping at u and continuing cannot beat the genuinely best route, because that combined route is just one particular way to reach v, and the shortest distance is the best over all ways.

Stated cleanly: let dist(x) be the true shortest distance from the source s to x. Then for every edge (u, v) with weight w(u,v), the triangle inequality says dist(v) <= dist(u) + w(u,v). The reason is immediate: the right-hand side is the cost of one specific route to v (a shortest route to u, then the single edge to v), and dist(v) is the minimum over ALL routes to v, so it cannot exceed any particular route's cost. This is the master invariant of the whole subject. It tells you exactly when relaxation has finished: once d[v] <= d[u] + w(u,v) holds for every edge — that is, no edge can be relaxed any further — the estimates have converged and equal the true distances.

This inequality is why all the algorithms are correct, and it is the basis of every termination and correctness proof in shortest paths. Dijkstra's, Bellman-Ford's, and the DAG method each work by relaxing edges until the triangle inequality holds everywhere; the moment it holds for all edges, d = dist. The same inequality also justifies negative-cycle detection: if after enough relaxations some edge can still be relaxed (the inequality is still violated), a negative cycle must be reachable, because otherwise the estimates would have settled.