Given an unweighted, undirected graph $G=(V,E)$ without loops or multiedges, and vertices $v,w$, one can use breadth-first search to check if $v$, $w$ are connected, and in particular the algorithm will return a shortest path between them. BFS has time complexity $O(|V|+|E|)=O(|V|^2)$.
Now let $k$ be some fixed integer (not part of the input). Is there an algorithm that takes $G$, $v,$ $w$, and checks whether there is a path between $v$ and $w$ of length $k$? What would be its time complexity?
The problem is NP-complete and referred to as Longest Path. It is FPT, though, so you can solve it in time polynomial in $n$ for fixed $k$.
If you want to solve it in FPT time, the easiest solution is to do color coding. The trick is two-fold.
Suppose that vertices are colored with $k$ colors, and you are looking for a rainbow-path of length $k$, i.e. a path where every vertex has different color. This problem can be solved by dynamic programming!
Repeat the following step: Randomly color the vertices of the graph with $k$ colors, and run the rainbow algorithm.
With probability depending only on $k$, if there exists a $k$-path, then you will output a rainbow path.
If the required path doesn't need to be simple, then there's a dynamic programming solution. Assume that the given graph is specified by an adjacency matrix $G$. Let $F_k(v, w)$ be the answer for input $k$, $v$ and $w$. So we have a formula:
$$ F_k(v, w) = \bigvee_u F_{k - 1}(v, u) \wedge G(u, w) $$
This kind of formula can be calculated using matrix multiplication: we use the AND operator instead of multiplication, and take the OR of them instead of the sum. Time complexity is $O(|V|^3 \log k)$.
