G is a connected, undiercted and unweighted graph, and s is some vertex ("source vertex").
For example, let's say the distance between u,v in G is 3, but there is a path of length 8 to v from u, so the algorithm should say that the distance between u,v is 8.
I thought of creating a new graph with same vertices with new edges, but I couldn't find the right ones. Thanks for the help.
Use a modification of Dijkstra, where you separate infor mation for odd and even distances:
To each node, add field $d_0$ and $d_1$. Initailly set $d_0(v)\leftarrow \infty$ and $d_1(v)\leftarrow\infty$ for all $v$
Set $d_0(s)\leftarrow 0$ and push $(s,1)$ to a queue.
Pop $(v,t)$ from the queue
For all neighbours $w$ of $v$: if $d_{t\bmod 2}(w)=\infty$, set $d_{t\bmod 2}(w)\leftarrow t$ and push $(w,t+1)$ to the queue.
If the queue is not empty, go back to step 3. Otherwise terminate. For each node $v$, $d_0(v)$ is the length of the shortest walk of even length from $s$ to $v$.
(It may be worth noting that the queue can be realized by an additional field of type pointer-to-node in each node)