Given a directed graph $D = (V,A)$ with edge-weights $w\in\mathbb{R}_{++}^A$ I'm trying to construct the following graph $D'=(V',A')$:
- For a fixed $v\in V$ we add a vertex $(v,0)$ to $V'$
- For every $(z,i)\in V'$ and $zu\in A'$ we add the vertex $(u,i+w_{zu})$ and the arc $(z,i)\to(u,i+w_{zu})$
- In each path of $D'$ the only vertex of $V$ that can be repeated is $v$ (and the path most end there)
For example if we have the graph $D=(V,A)$ with:
$$V = \{u,v,x,y,z,a\}$$ $$A = \{vz,zu,uv,vy,yx,xv,xu,xa\}$$
the new graph will be given by
- $(v,0)\to(z,w_1)\to(u,w_2)\to(v,w_3)$
- $(v,0)\to(y,w_4)\to(x,w_5)\to(v,w_6)$
- $(x,w_5)\to(u,w_7)\to(v,w_8)$
- $(x,w_5)\to(a,w_9)$
where the $w$'s are the respective sums of the weights.
At first I tried to attack this problem using a DFS type of approach, but given that the nodes can be repeated under certain conditions I got stuck and with no clues on how can this graph be constructed (algorithmically). Any ideas?