Aflarea drumului minim. Arborele drumurilor minime

Parcurgerea în lățime a grafurilor are două proprietăți foarte valoroase: prima - permite determinarea tuturor nodurilor accesibile din unul dat (componenta sa conexă); a doua - permite determinarea unui drum minim (ca număr de muchii) între nodul de start și toate cele în care se poate ajunge din el. Dacă la o parcurgere în lățime dintr-un nod dat, de fiecare dată când se avansează într-un nod încă nevizitat, se notează ca muchie perechea dintre nodul curent și cel în care se avansează, obținem un arbore de acoperire a componentei conexe. În acest arbore, orice lanț elementar între nodul de pornire și alt nod are lungime minimă dintre toate lanțurile ce există în graf între cele două noduri (considerând lungimea lanțului ca fiind numărul de muchii).