Show that problem of Shortest-Path in digraph is in NL

Question

Look at solution to exercise 2, please.
Exercise and solution is derieved from: https://people.eecs.berkeley.edu/~luca/cs172-07/solutions/sol8.pdf

$$ShortestPath = \{(G, k, s, t)| \text{the shortest path from $s$ to > $t$ in $G$ has length $k$}\}$$ (a) Prove that $ShortestPath$ is in $NL$.

(a) Solution: We construct a $NL$-machine for ShortestPath as follows: on input $\langle G, k, s, t\rangle$, first compute $r_{k−1}$ (the number of vertices reachable from $s$ in at most $k − 1$ steps). Then, on input $\langle G = (V, E), k, s, t\rangle$ and $r_{k−1}$ on the work tape,

d ← 0
flag ← FALSE
for all w ∈ V do
p ← s
for i ← 1 to k − 1 do
non-deterministically pick a neighbor q of p
if p = w then
d ← d + 1
if w = t reject
if w is a neighbor of t then
flag ← TRUE
if d < r_{k−1} reject
if flag then accept else reject  

I don't know why it is so complex.
Tell me please, why direct and simple algorithm is not ok:
Check if there exists path from $s$ to $t$ of length $1$
Check if there exists path from $s$ to $t$ of length $2$
...
Check if there exists path from $s$ to $t$ of length $k-1$
If there exists path of length $\le k -1 $ then reject. Else check if exists length of $k$ and accept if exists.

In other words we check one be one each length. We can check existence of path thanks to non-determinism. We launch number of visited nodes and check if we end up in $t$

Answer 1

The difficulty here is how to check using non-deterministic logarithmic space that there is no path from $s$ to $t$ of some length $\ell$. We cannot just go over all possible paths of length $\ell$ since in order to do this we will need to "remember" $\ell$ vertices, whereas we are only allowed to remember $O(1)$ vertices (since each vertex takes up $\Theta(\log n)$ space).

If we want to check that there exists a path of length $\ell$, we can simply guess the path vertex-by-vertex and check that it leads from $s$ to $t$; this only requires counting up to $\ell$, which takes logarithmic space (since we're only interested in $\ell < n$). But it's not so clear how to check that there doesn't exist a path of length $\ell$ – what would be a witness for that?

The solution is to use the technique of inductive counting, invented for the proof of the Immerman–Szelepcsényi theorem, which states that NL=coNL. This is what the solution uses.