Néha szükségünk lehet annak ismeretére, hogy létezik-e két csúcs között vezető út a gráfban. Ezért csak azzal fogunk foglalkozni, hogy egy irányított vagy irányítatlan gráfban honnan hova lehet eljutni, ezért elegendő csak egy mátrixot használni. Az eljutás módja és költsége most nem érdekes.

Definíció (tranzitív lezárt):

• A $G = (V, E)$ gráf tranzitív lezártja alatt a $T \subseteq V \times V$ relációt értjük, ahol $(u, v) \in T \iff$ ha $G$-ben az $u$ csúcsból elérhető a $v$ csúcs.

A tranzitív lezárt kiszámításához használhatjuk a Warshall algoritmust, amely a Floyd-Warshall algoritmus egy módosított változata. Az algoritmusban előforduló két aritmetikai műveletet, a $min$-t és a $+$-t, két logikai műveletre, $\lor$-ra (logikai VAGY) és $\land$-re (logikai ÉS) cseréljük. Egy $T/1 : \mathbb{B} [n, n]$ $n \cdot n$-es logikai mátrixot használunk, amelyben $T^{(k)}_{ij}$ értéke igaz (1), ha az $i$ és $j$ cimkéjű csúcsok között vezet út, és $T^{(k)}_{ij}$ értéke hamis (0), ha az $i$ és $j$ cimkéjű csúcsok között nem vezet út.

Műveletigény:

A Floyd–Warshall-algoritmussal megegyezően a futási idő $\Theta (n^3)$ lesz. A gyakorlatban gyorsabban hajtódnak végre a logikai műveletek, mint az egész számokon végzett aritmetikai műveletek.

További előny a tranzitív lezárt közvetlen keresésekor, hogy az egész értékek helyett csak logikai értékeket kell tárolni. Így a tárigény a Floyd–Warshall-algoritmushoz képest annyiszor kisebb, amennyi bitet gépünk egy egész szám tárolására használ.