Edge relaxations: Predecessor subgraph is a rooted tree

Dependencies:

1. Path in Graph
2. Edge relaxations
3. Rooted tree
4. Acyclic predecessor graph is union of rooted trees

Let $G$ be a weighted graph where no negative-weight cycles are reachable from $s \in V$. Let $G_π = (V_π, E_π)$ be the predecessor subgraph of $G$ with source $s$ obtained via relaxations. Then $G_π$ is a tree rooted at $s$.

Proof

$G_π$ is acyclic. See CLRS lemma 24.16, Section 24.5, page 674, third edition for a proof.

Since $G_π$ is an acyclic predecessor graph, it is a union of rooted trees.

Since roots of these trees have in-degree 0, and $s$ is the only element in $V_π$ with in-degree 0 (the others have in-degree 1), only $s$ can be a root. Therefore, $G_π$ is a rooted tree.

Dependency for:

1. Edge relaxations: Predecessor subgraph is a shortest-path tree after convergence

Info:

• Depth: 4
• Number of transitive dependencies: 10

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. Transpose of a graph
6. Path in Graph
7. Triangle inequality of shortest paths
8. Edge relaxations
9. Rooted tree
10. Acyclic predecessor graph is union of rooted trees