[Solved]: Shortest even path that goes through a vertex

Problem Detail: 

Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \{s,t\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least once) and is of even length (regarding number of edges).

We need to find such a path that is the shortest in $O(V+E)$ time.

I thought about BFS from $s$ to find a shortest path to $d$, and BFS from $d$ to find shortest path to $t$, but then it wouldn't necessarily be of even length. Plus, such a path we're looking for is not necessarily simple.

Any hints?

Asked By : TheNotMe

Answered By : Hendrik Jan

Your remark is true: there might be no simple even path from $s$ to $t$, an even path perhaps includes a cycle of odd length.

The shortest path from $s$ to $t$ via $d$ is the shortest path from $s$ to $d$ plus the shortest path from there to $t$.

To compute even length paths you might consider turning the graph into a bipartite graph using two copies of itself. Double $V$ by adding a copy $V'$. Now duplicate every edge $(x,y)$ into $(x,y')$ and $(x',y)$, where the primes indicate copies in $V'$. Now the shortest path from $s$ to $t$ will be of even length. (And all paths of even length in the original graph are 'represented' in the new graph.)

Problem: the intermediate node $d$ might be $d'$, its copy in $V'$. Your turn to connect the two requirements 'via $d$' and 'even length'.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26047