Relaxation of an edge in Dijkstra's algorithm

Question

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 1

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.

Answer 2

The relaxation process in Dijkstra's algorithm refers to updating the cost of all vertices connected to a vertex v, if those costs would be improved by including the path via v.

Answer 3

Relaxing an edge, (a concept you can find in other shortest-path algorithms as well) is trying to lower the cost of getting to a vertex by using another vertex.

You are calculating the distances from a beginning vertex, say S, to all the other vertices. At some point, you have intermediate results -- current estimates. The relaxation is the process where you check, for some vertices u and v:

if directly_connected(v, u)
    if est(S, v) > est(S, u) + dist(u,v)
       est(S, v) = est(S, u) + dist(u, v)

where est(S,a) is the current estimate of the distance, and dist(a,b) is the distance between two vertices that are neighbors in the graph.

What you are basically checking in the relaxation process is weather your current estimate from a to b could be improved by "diverting" the path through c (this "diversion" would be the length of a path from a to c and from c to b).

Answer 4

Edge relaxation process

Initialization

In shortest-path algorithms, you first assign a path-cost of zero to a starting node (e.g. S), and a path-cost of infinity to every other node (e.g. A, E).

S := new Node()
A := new Node()
E := new Node()

// To go from S to S is zero
S.path_cost = 0

// high cost
A.path_cost = 1000 // "infinity"
E.path_cost = 1000 // "infinity"

Edge relaxation

Infinity is the highest cost we could have, so we want to reduce "relax" that to a lower cost if possible. To do that we compute the cost of a path (e.g. a or ab) between the starting node and another node, and update the path-cost for the node, if that path cost is less.

a := 3
b := 5

SS := S.path_cost + 0
if (S.path_cost > SS) {
  // 0 !> 0 + 0
  S.path_cost = SS
}

Sa := S.path_cost + a
if (A.path_cost > Sa) {
  // 1000 > 0 + 3
  A.path_cost = Sa
  // A = 0 + 3
}

ab := A.path_cost + b
if (E.path_cost > ab) {
  // 1000 > 3 + 5
  E.path_cost = ab
  // E = 3 + 5
}

Edge relaxation repeated

c := 1

Sc := S.path_cost + c
if (E.path_cost > Sc) {
  // 8 > 0 + 1
  E.path_cost = Sc
  // E = 0 + 1
}