0
$\begingroup$

I am trying to think of an algorithm such that giving a graph $G(V,E)$, and a weight function $w\colon E \to \mathbb{N}_+$ (which means giving every edge in the graph a positive weight), and a source vertex $S$, the algorithm finds the shortest path between each $v \in V$ and $S$, such that the weight of the path is divided by 3 . (The weight of the path means the sum of all the weights of the edges that are on the path.)

In some solutions, I found that for this problem they built a new auxiliary graph which will "maintain the weight modulo 3" so that when we get from $S$ to any vertex we will be interested in the path that starts and ends with remainder 0 and this is through duplicating the graph to 3 copies which will allow switching between different copies.

I don’t understand how to build such a graph and how it is going to help me with this problem, any help would be appreciated.

New contributor
mmolaan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
0
$\begingroup$

Given $G=(V,E,w)$ the auxiliary graph you want to build is $H=(V', E', w')$ where:

  • $V' = V \times \{0,1,2\}$
  • Given $(u,i), (v,j) \in V'$, $( (u,i), (v,j) ) \in E'$ if and only if $(u,v) \in E$ and $i+w(u,v) \equiv j \pmod{3}$.
  • For any $e' =( (u,i), (v,j) ) \in E'$, $w'(e') = w(u,v)$.

For any vertex $v \in V$, a shortest path $\pi'$ between $(S,0)$ and $(v, 0)$ in $H$ induces a path $\pi$ from $S$ to $v$ in $G$ that is shortest among those having length divisible by $3$. In details, let $\langle v'_0, v'_1, \dots, v'_k \rangle$ be the vertices traversed by $\pi'$, where $v'_j = (v_j, i_j)$. The path $\pi$ traverses the vertices $\langle v_0, v_1, \dots, v_k\rangle$, in order.

$\endgroup$
4
  • $\begingroup$ how can i prove this ? i understand the algorithm but how to actually prove it $\endgroup$ – mmolaan Jun 8 at 18:46
  • $\begingroup$ Prove that given any path $\pi$ of length $3k$, for $k \in \mathbb{N}$, from $S$ to a generic vertex $v$ in $G$, there exists a path $\pi'$ of length $3k$ from $S$ to $(v, 0)$ in $H$. This implies that a shortest path in $H$ is not longer than the shortest path in $G$. Then prove that, given any path $\pi'$ from $S$ to a generic vertex of the form $(v,0)$ in $H$ you have that: (i) the length of $\pi'$ is a multiple of $3$, and (ii) there is a path $\pi$ in $G$ from $S$ to $v$ having the same length as $\pi'$. This shows that a shortest path in $H$ is not shorter than the shortest path in $G$.. $\endgroup$ – Steven Jun 8 at 19:45
  • $\begingroup$ ...and also provides a constructive way to find $\pi$ from $\pi'$. I actually already described how to find $\pi$ in my answer so you just have to prove (i) and that the lengths of $\pi$ and $\pi'$ coincide. $\endgroup$ – Steven Jun 8 at 19:47
  • $\begingroup$ thank you so much ! $\endgroup$ – mmolaan Jun 8 at 19:54

Your Answer

mmolaan is a new contributor. Be nice, and check out our Code of Conduct.

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.