Shortest Path Example

Consider nodes $1$, $2$, $3$, $4$ with edges: $1 \to 2$ (weight $1$), $1 \to 3$ (weight $4$), $2 \to 3$ (weight $2$), $2 \to 4$ (weight $5$), $3 \to 4$ (weight $1$). Topological order: [$1$, $2$, $3$, $4$]. Start with $dist = [0, \infty, \infty, \infty]$. Process node $1$: Relax edges to $2$ and $3$.

Now $dist = [0, 1, 4, \infty]$. Process node $2$: Relax edges to $3$ and $4$. Now $dist = [0, 1, 3, 6]$. Process node $3$: Relax edge to $4$. Now $dist = [0, 1, 3, 4]$. Final answer: shortest distances are [$0$, $1$, $3$, $4$].