0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Hagen von Eitzen Jun 11 at 14:04
  • $\begingroup$ Is the graph guaranteed to not be bipartite? $\endgroup$ – Hagen von Eitzen Jun 11 at 14:06
  • $\begingroup$ @HagenvonEitzen It can be, G can be any undirected connected graph. $\endgroup$ – Omri Attal Jun 11 at 14:08
  • $\begingroup$ @HagenvonEitzen yes, it is valid, it doesn't necessarily have to be simple path. $\endgroup$ – Omri Attal Jun 11 at 14:09
0
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Omri Attal Jun 11 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.