Now for each vertex it is easy to check whether it lies on any shortest path between $a$ and $b$:

the criterion is the condition $d_a[v] + d_b[v] = d_a[b]$.

* Find the shortestpath of even length from a source vertex $s$ to a target vertex $t$ in an unweighted graph:

* Find the shortestwalk of even length from a source vertex $s$ to a target vertex $t$ in an unweighted graph:

For this, we must construct an auxiliary graph, whose vertices are the state $(v, c)$, where $v$ - the current node, $c = 0$ or $c = 1$ - the current parity.

Any edge $(u, v)$ of the original graph in this new column will turn into two edges $((u, 0), (v, 1))$ and $((u, 1), (v, 0))$.

After that we run a BFS to find the shortestpath from the starting vertex $(s, 0)$ to the end vertex $(t, 0)$.

After that we run a BFS to find the shortestwalk from the starting vertex $(s, 0)$ to the end vertex $(t, 0)$.<br>**Note**: This item uses the term "_walk_" rather than a "_path_" for a reason, as the vertices may potentially repeat in the found walk in order to make its length even. The problem of finding the shortest_path_ of even length is NP-Complete in directed graphs, and[solvable in linear time](https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230140403) in undirected graphs, but with a much more involved approach.