Przynależność do klasy NL Przyjmujemy na wejściu algorytmu niedeterministycznego dane w postaci (G, x, y). Używamy zmiennej pomocniczej v zainicjowanej wartością x. W każdym kroku korzystając z niedeterminizmu wybieramy kolejny wierzchołek grafu sąsiedni z v, który przypisujemy do v. Jeżeli wybrany wierzchołek v = y to algorytm kończy się i zwraca odpowiedź pozytywną, w przeciwnym razie powtarzany jest krok poprzedni. Formalnie, algorytm powinien zawierać również licznik wykonanych kroków, w przypadku gdy licznik przekroczy całkowitą liczbę wierzchołków grafu G algorytm kończy się z odpowiedzią negatywną.
Algorytmy dla maszyn deterministycznych Algorytm Floyda-Warshalla lub algorytm Dijkstry może zostać wykorzystany w celu sprawdzenia istnienia ścieżki pomiędzy dowolnymi dwoma wierzchołkami grafu skierowanego. Wymienione algorytmy oprócz odpowiedzi na pytanie czy istnieje ścieżka dają również informacje na temat długości najkrótszej ścieżki co wiąże się z wyższą złożonością obliczeniową i pamięciową.
Przeszukiwanie wszerz lub w głąb pozwala sprawdzić