I'm not sure what the relaxation function in Dijkstra algorithm does. Here is my current understanding:
The relaxation function is essentially deciding which edge to choose from different alternatives that lead to the same vertices. If there is three different edges you can take from your vertex A to your vertex Z, the relaxation function will make sure to choose the one who makes the cost of the overall trail lower.
$\endgroup$1 Answer
$\begingroup$From CLRS (3rd ed.),
The process of relaxing an edge $(u, v)$ consists of testing whether we can improve the shortest path to $v$ found so far by going through $u$ and if so, updating $v{.}d$ and $v{.}\pi$. A relaxation step may decrease the value of the shortest-path estimate $v{.}d$ and update $v$'s predecessor attribute $v{.}\pi$.
Simply put, the relaxation function checks whether going to a vertex $v$ from a source vertex $s$ through an intermediary vertex $u$ reduces the current shortest distance from $s$ to $v$. If it does, we add $u$ to the shortest path from $s$ to $v$, and update the shortest distance of $v$ from $s$ (i.e., $v{.}d$ in the paragraph above) and the predecessor of $v$ (i.e., $v{.}\pi$ in the paragraph above) accordingly. If not, we simply do not add $u$ to the shortest path from $s$ to $v$.
$\endgroup$
