Shortest-path tree

Dependencies:

1. Path in Graph
2. Rooted tree

For a graph $G = (V, E)$, a shortest-path tree $T = (V', E')$ with source $s \in V$ is a directed subgraph of $G$ satisfying all these properties:

1. $v \in V' \iff \delta(s, v) \neq \infty$
2. $T$ is a tree rooted at $s$.
3. $\forall v \in V'$, the unique path from $s$ to $v$ in $T$ is a shortest path from $s$ to $v$ in $G$.

Dependency for:

1. Breadth-first search
2. Edge relaxations: Predecessor subgraph is a shortest-path tree after convergence

Info:

• Depth: 3
• Number of transitive dependencies: 6

Transitive dependencies:

1. /sets-and-relations/equivalence-classes
2. /sets-and-relations/relation-composition-is-associative
3. /sets-and-relations/equivalence-relation
4. Graph
5. Path in Graph
6. Rooted tree