# Relaxation of an edge in Dijkstra's algorithm

AlgorithmGraph TheoryGraph Algorithm## Algorithm Problem Overview

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.

## Algorithm Solutions

## Solution 1 - Algorithm

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.

## Solution 2 - Algorithm

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.

## Solution 3 - Algorithm

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*).

## Solution 4 - Algorithm

### 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
}
```

## Solution 5 - Algorithm

lets suppose in graph if we have (u,v)∈ E where w(u,v)=10 then if by adding a third vertex in between them like w(u,y)=1 and w(y,v)=3 now we find a path between u and v with weight 1+3=4<10. Now we will consider the second path as shortest which is (u,y,v) and will ignore the first one, this is relaxation.

## Solution 6 - Algorithm

Edge relaxation.

> To relax an edge v -> w means to test whether the best-known way from > s to w is to from s to v, then take the edge from v to w, and, if so, > update our data structures.

Java code:

```
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to;
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
```

There is also vertex relaxation. That means to relax all the edges pointing from a given vertex.

```
private void relax(EdgeWeightedGraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
relax(e);
}
}
```

## Solution 7 - Algorithm

Take a look at https://www.youtube.com/watch?v=2E7MmKv0Y24&t=1336s Time: 28:30. Funny thing is that the shortest paths are the ones that are under TENSION. To me this is the exact opposite of RELAX. Oh well.