Algorithm that finds the shortest even distance from a vertex s in a graph G to all other vertices.

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.

• Would something like $u\to \color{red}a\to b\to c\to \color{red}a\to d\to v$ be valid? (I am asking because not all authors distinguish walks, trails, and paths the same way) – Hagen von Eitzen Jun 11 at 14:04
• Is the graph guaranteed to not be bipartite? – Hagen von Eitzen Jun 11 at 14:06
• @HagenvonEitzen It can be, G can be any undirected connected graph. – Omri Attal Jun 11 at 14:08
• @HagenvonEitzen yes, it is valid, it doesn't necessarily have to be simple path. – Omri Attal Jun 11 at 14:09

Use a modification of Dijkstra, where you separate infor mation for odd and even distances:

1. 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$$

2. Set $$d_0(s)\leftarrow 0$$ and push $$(s,1)$$ to a queue.

3. Pop $$(v,t)$$ from the queue

4. 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.

5. 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)

• Thanks for the help! But, Can you explain these lines: Set d0(s)←0 and push (s,1) to a queue. Pop (v,t) from the queue – Omri Attal Jun 11 at 14:46