$\star$ Notations and Variables

$u\to v$: the directed edge between vertex $u$ and $v$

$u\leadsto v$: the path that connects vertex $u$ and $v$

$\ce{dist}: \texttt{\gray{\blue{Map}<\blue{Vertex}, \blue{int}\,|\,\purple{$\infty$}>}}$

• Keeps track of the distance from the starting vertex to any other vertex.
• Initializes to $0$ for the starting vertex, $\infty$ for other vertices.

$\ce{pred}:\texttt{\gray{\blue{Map}<\blue{Vertex}, \blue{Vertex}\,|\,\purple{null}>}}$

• Keeps track of the predecessor of any given vertex.
• Initializes to null for all vertices.

Def. Tense Edge

An edge $u\to v$ is tense if:

$$ \ce{dist}[u] + \ce{weight}(u\to v) < \ce{dist}[v] $$

@Hint If $u\to v$ is tense, then the distance from start to $v$ can be improved by including $u$ as the predecessor of $v$.

Combining ${\tt{start}}\rightsquigarrow u$ and $u\to v$ is better than the current ${\tt{start}}\rightsquigarrow v$.

Def. Relax a Tense Edge

If $u\to v$ is tense, we relax it by:

function RelaxEdge(u→v: Edge):
	dist[v] = dist[u] + weight(u→v)
	pred[v] = u

Improve $\text{dist}[v]$ by including $u$ as the predecessor of $v$.

Go to next: