patternMinor
An efficient algorithm to find a shortest cycle including a specific vertex
Viewed 0 times
cycleshortestvertexefficientalgorithmincludingfindspecific
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#57669, answer score: 9
Revisions (0)
No revisions yet.