# an algorithm to find the shortest path between two vertices whose weight is divided by 3?

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.

## 1 Answer

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.

• how can i prove this ? i understand the algorithm but how to actually prove it – mmolaan Jun 8 at 18:46
• 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$.. – Steven Jun 8 at 19:45
• ...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. – Steven Jun 8 at 19:47
• thank you so much ! – mmolaan Jun 8 at 19:54