Transitive Closure

Vi vil finne ut hvilke noder som kan nå hverandre, vekting er irrelevant. Gitt en graf, $G$, får vi ut en ny graf $G^{\ast }=(V^{\ast },E^{\ast })$ der kant $(u,v)$ er i $E^{\ast }$ er $1$ eller $0$ avhengig av om det finnes en sti mellom $u$ og $v$.

---

Pseudokode og kjøretid

Kjøretid: $\Theta (n^3)$

Virkemåte

Prinsipp: Hvis det finnes en vei fra $A$→$B$ og $B$→$C$, så finnes det en vei fra $A$→$C$.

Sentral formel er

$$t_{ij}^{(k)}=t_{ij}^{(k-1)}\vee (t_{ik}^{(k-1)}\wedge t_{kj}^{(k-1)})$$

Der vi itererer oss gjennom mange matriser for å finne om det er veier mellom eller ikke.