Vi vil finne ut hvilke noder som kan nå hverandre, vekting er irrelevant. Gitt en graf, , får vi ut en ny graf der kant er i er eller avhengig av om det finnes en sti mellom og .


Pseudokode og kjøretid

Kjøretid:

Virkemåte

Prinsipp: Hvis det finnes en vei fra → og →, så finnes det en vei fra →.

Sentral formel er

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