Edge Relaxation Property for Dijkstra’s Algorithm and Bellman Ford’s Algorithm

In the field of graph theory, various shortest path algorithms especially Dijkstra’s algorithm and Bellmann-Ford’s algorithm repeatedly employ the use of the technique called Edge Relaxation. 

The idea of relaxation is the same in both algorithms and it is by understanding, the ‘Relaxation property‘ we can fully grasp the working of the two algorithms.  

Relaxation:

The Edge Relaxation property is defined as the operation of relaxing an edge u → v by checking whether the best-known way from S(source) to v is to go from S → v or by going through the edge u → v. If it is the latter case we update the path to this minimum cost.

Initially, the reaching cost from S to v is set infinite(∞) and the cost of reaching from S to S is zero.

 

Representing the cost of a relaxed edge v mathematically,

d[v] = min{ d[v], d[u] + c(u, v) } 

And the basic algorithm for Relaxation will be :

if ( d[u] + c(u, v) < d[v] ) then

{
d[v] = d[u] + c(u, v)
}

where d[u] represents the reaching cost from S to u

d[v] represents the reaching cost from S to v
c(u, v) represents reaching cost from u to v

Solving Single Source Shortest Path problem by Edge Relaxation method

• In single-source shortest paths problems, we need to find all the shortest paths from one starting vertex to all other vertices. It is by relaxing an edge we test whether we can improve this shortest path(via the greedy approach method).
• This means that during traversing the graph and finding the shortest path to the final node, we update the costs of the paths we have for the already known nodes as soon as we find a shorter path to reach it. 
• The below example, will clear and fully explain the working of the Relaxation property.
• The given figure shows graph G and we have to find the minimum cost to reach B from source S.

 

Input: graph – G

Let A be u and B be v.

The distance from source to the source will be 0.
=> d[S] = 0

Also, initially, the distance between other vertices and S will be infinite.

INITIALIZE – SINGLE SOURCE PATH (G, S)

for each vertex v in the graph

d[v] = ∞
d[S] = 0

Initialization of graph

Now we start relaxing A.

The shortest path from vertex S to vertex A is a single path ‘S → A’.

d[u] = ∞

Because, d[S] + c(S, u) < d[u]
d[u] = d[S] + c(S, u) = 0 + 20
=> d[u] = 20

Graph after relaxing A

Now we relax vertex B. 

The process remains the same the only difference we observe is that there are two paths leading to B. 

The path I: ‘S→B’
Path II: ‘S→A→B’

First, consider going through the path I – d[v] = ∞

Because, d[S] + c(S, v) < d[v]
d[v] = d[S] + c(S, v) = 0 + 40
=> d[v] = 40

Since its a lower value than the previous initialized d[v] is updated to 40, but we will now proceed to checking path II as per the greedy method approach.

d[v] = 40
Because, d[u] + c(u, v) < d[v]
d[v] = d[u] + c(u, v) = 20 + 10
=> d[v] = 30

Since the new d[v] has a lower cost than the previous of case I we again update it to the new obtained by taking path II. We cannot update the d value to any lower than this, so we finish the edge relaxation.

Final Graph with smallest cost to reach the vertices A and B after relaxing B

Ultimately we get the minimum cost to reach each other vertices in the graph from the source and hence solving the single source shortest path problem.

Finally, we can conclude that the algorithms for the shortest path problems (Dijkstra’s Algorithm and Bellman-Ford Algorithm) can be solved by repeatedly using edge relaxation.