Given an undirected graph $G$ of $N$ nodes and a starting node $s$, I want to build, with dynamic programming, a table whose $(k, n)$-th entry is $1$ if node $n$ is reachable with exactly $k$ steps from node $s$.
Specifically, for the first row of the table, I set $(1, n)$ to 1 if node $n$ is connected to node $s$. Then for the second row, I set $(2, n)$ to 1 if node $n$ is connected to any of the nodes who have value $1$ in the first row. I can stop the construction whenever I have a repeated row. In other words, I want to build the table to the point where more rows will be redundant, as there are already exact copies of them up in the table. So $k$ should be expressed in terms of $N$.
I want to check if this table construction can be done in polynomial time. I think it boils down to whether the number of rows is polynomially bounded. Is it so?
My intuition is yes, because in the worst case, where the $N$ nodes are serially connected one next to another, and starting node $s$ is at one end, I can still reach the other end with $N-1$ steps.