Relaxation of an edge in Dijkstra's algorithm

algorithm graph-theory graph-algorithm
Geek picture Geek · Oct 8, 2012 · Viewed 40.5k times · Source

What does relaxation of an edge mean in the context of graph theory ? I came across this while studying up on Dijkstra's algorithm for single source shortest path.

Answer

krjampani picture krjampani · Oct 8, 2012

Here's a nice description of the Algorithm that also explains the notion of relaxation.

The notion of "relaxation" comes from an analogy between the estimate of the shortest path and the length of a helical tension spring, which is not designed for compression. Initially, the cost of the shortest path is an overestimate, likened to a stretched out spring. As shorter paths are found, the estimated cost is lowered, and the spring is relaxed. Eventually, the shortest path, if one exists, is found and the spring has been relaxed to its resting length.

Related questions

When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)?

I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other? Could anyone give any examples of how DFS would trump BFS and vice versa?

Read More
Finding all cycles in a directed graph

How can I find (iterate over) ALL the cycles in a directed graph from/to a given node? For example, I want something like this: A->B->A A->B->C->A but not: B-&…

Read More
Find all paths between two graph nodes

I am working on an implemtation of Dijkstras Algorithm to retrieve the shortest path between interconnected nodes on a network of routes. I have the implentation working. It returns all the shortest paths to all the nodes when I pass …

Read More