Construct a TM to show that {<G,s,t,k> | G is a directed graph with path length $\le$ k from s to t} is in class P

Question

I would like to construct a deterministic TM that decides $L=${$<G,s,t,k>$ | $G$ is a directed graph that has a path of length at most $k$ from vertex $s$ to vertex $t$} in polynomial time.

So far, my construction is as follows.

$M=$"On input $<G,s,t,k>:$

1. For each path $p$ from $s$ to a vertex $v \in G$ of $k$ length:

------1.0 Clear all marks from vertices in $G$.

------1.1 Mark the vertices in $p$.

------1.2 Scan input. If $t$ is marked, accept.

2. Reject, since $t$ is not within $k$ steps from $s$."

(1.0), (1.1), and (1.2) are each $O(n)$, and $(2)$ is $O(1)$.

However, I think (1) is $O(n!)$.

What is a better approach that would make this $O(n^m)$ (i.e., polynomial)?

Edit:

The TM does not have to be "rigorously made".

For example, to find determine whether PATH={<G,s,t>| G is a directed graph that has a path from s to t} is in $P$, the following TM is acceptable:

M="On input <G,s,t>"

1. Mark vertex s.

2. Repeat until no additional vertex is marked:

------Scan all edges of G. If there is an edge from a marked vertex u to an unmarked vertex v, mark v.

3. If t is marked, accept. Otherwise, reject."

((1) is $O(1)$, (2) is $O(\#$of edges $*\#$of vertices$)=O(n^2*n=n^3)$, and (3) is $O(1)$).

Answer 1

Given a sequence of vertices $(s, v_1, \ldots, v_m, t)$, where $0 \leq m \leq k-1$, how many operations does it take to decide whether the sequence defines a path in $G$? How many such sequences are there?

Answer 2

A polynomial time algorithm is for example a slightly modified breadth first search:

Start with $s$ and consider all neighbors. Then consider all the neighbor‘s neighbors etc. up to level $k$. If you found $t$ along the way (you might as well stop the algorithm in this situation) the graph $G$ is in your class, otherwise not.

If $\Delta$ denotes the maximal outgoing degree of $G$ this algorithm has a runtime bounded by $\Delta + \Delta^2 + ... + \Delta^k$ hence is in $\mathcal{O}(\Delta^k)$. This is of cause polynomial in the number of vertices $n$, the number of edges $m$ and the maximal degree $\Delta$, but it is exponential in $k$.