DAG legrövidebb utak egy forrásból (Single-source shortest paths in DAGs)

Animáció

Struktogram

$DAGshortestPaths(G : \mathcal{G}_{w};s : \mathcal{V}) : \mathcal{V}$
$S : Stack$
$dcg : \mathcal{V}$
$dcg := \emptyset$
$topologicalSort(G,s,dcg,S)$
$dcg = \emptyset$
$DAGshPs(G,S)$ $\text{SKIP}$
$\text{return} \space dcg$

$topologicalSort(G : \mathcal{G};s : \mathcal{V}; \&dcg : \mathcal{V};S : Stack)$
$\forall u \in G.V$
$color(u) := white$
$\pi(u):=\emptyset$
$DFvisit(G,s,dcg,S)$

$DFvisit(G : \mathcal{G};u : \mathcal{V}; \&dcg : \mathcal{V}; S : Stack)$
$color(u) := grey$
$\forall v \in G.A(u) \space while \space dcg = \emptyset$
$color(v) = white$
$\pi (v) := u$
$color(v) = grey$
$DFvisit(G, v, dcg, S)$ $\pi(v) := u; dcg := v$ $\text{SKIP}$
$color(u) := black$
$S.push(u)$

$DAGshPs(G : \mathcal{G}_{w};S : Stack)$
$\forall v \in G.V$
$d(v) := \infty$
$\pi(v):=\emptyset$
$s := S.pop()$
$d(s) := 0$
$u := s$
$\lnot S.isEmpty()$
$\forall v \in G.A(u) \land d(v) > d(u) + G.w(u,v)$
$\pi(v) := u$
$d(v) := d(u) + G.w(u,v)$
$u := S.pop()$

Feladatok