Why do we call it "Relaxing" an edge?

dijkstra bellman-ford
Eric G picture Eric G · May 25, 2012 · Viewed 9.1k times · Source

In Dijkstra's shortest path algorithm and others, to examine an edge to see if it offers a better path to a node is referred to as relaxing the edge. Why is it called relaxing?

Answer

Charlie Martin picture Charlie Martin · May 25, 2012

In general mathematically, relaxation is making a change that reduces constraints. When the Dijkstra algorithm examines an edge, it removes an edge from the pool, thereby reducing the number of constraints.

It's not horribly useful terminology, but think how cool you'll sound saying it.

Related questions

Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?

After a lot of Googling, I've found that most sources say that the Dijkstra algorithm is "more efficient" than the Bellman-Ford algorithm. But under what circumstances is the Bellman-Ford algorithm better than the Dijkstra algorithm? I know "better" is a …

Read More
Am I right about the differences between Floyd-Warshall, Dijkstra's and Bellman-Ford algorithms?

I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you. Dijkstra's algorithm is used only when you have a single source and …

Read More
Can Dijkstra's Single Source Shortest Path Algorithm detect an infinite cycle in a graph?

So I came to this beautiful problem that asks you to write a program that finds whether a negative infinity shortest path exists in a directed graph. (Also can be thought of as finding whether a "negative cycle" exists in …

Read More