Menu
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?
838
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.
The single - source shortest paths are based on a technique known as relaxation, a method that repeatedly decreases an upper bound on the actual shortest path weight of each vertex until the upper bound equivalent the shortest - path weight.
Relaxation is the most important step in Bellman-Ford. It is what increases the accuracy of the distance to any given vertex. Relaxation works by continuously shortening the calculated distance between vertices comparing that distance with other known distances.
Dijkstra's and Bellmann Ford's algorithm use a technique called edge relaxation. This means that during traversing our graph and finding our shortest path, we update the paths we have for already known nodes as soon as we find a shorter path to reach it.
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.
101
I do not think the question is related to the mathematical concept talked about in the current accepted answer. I am basing my answer on the second edition of Cormen's (CLRS) book, specifically on chapter 24 in a section about relaxation.
Context: You are searching for the shortest path between a node s and all the other nodes. Imagine you have two nodes u and v. You already have an intermediate path for them.
relax(u,v) is a function that should be read as "relax v using u". I prefer to understand the function as "shorten v's distance to s using u". You are asking yourself if you should give up on your current path s-v in favor of transforming it into s-u-v. All you have to do to see if the distance of s-u plus the additional cost of the arrow u-v are better than the distance s-v. The picture examplifies the function
A picture from CLRS's explanation on Relaxation
29
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
