# An efficient algorithm to find a shortest cycle including a specific vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$.

We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle.

This answer on SO explains why neither BFS or DFS work. However, I still think that DFS could be helpful in finding a minimun such cycle. Is there a way to make it work?

• That seems to be explained in the SO post as well. I don't see what your question is now. Community votes, please: unclear?
– Raphael
May 20 '16 at 12:32
• @Shaull I tried hard to solve it with DFS It might be cause of that I didn't see how BFS works well. Thanks. May 20 '16 at 14:21

You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).
An important property of BFS is that if it runs from vertex $v$, then every vertex $s$, when it is first reached, then the path that was found from $v$ to $s$ is minimal. Thus, reaching $v$ from $v$ with BFS finds the shortest path from $v$ to itself, namely the shortest cycle that contains $v$.