# Shortest walk from $u$ to $v$ through $w$

We have an undirected, weighted graph $$G=(V, E)$$ with two weight functions $$W_1 : E \rightarrow \mathbb{R}^{+}$$ and $$W_2 : E \rightarrow \mathbb{R}^{+}$$ such that for every $$e \in E$$ we have $$W_1(e) > W_2(e)$$.

The length of a walk $$\sigma$$ is calculated in such a way that for every edge $$e \in E$$, for the first appearance of $$e$$ in $$\sigma$$ we calculate the weight of $$e$$ by $$W_1(e)$$, and for reminding appearances of $$e$$ in $$\sigma$$ we calculate the weight of $$e$$ by $$W_2(e)$$.

The goal is to find the shortest walk from $$u$$ to $$v$$ through $$w$$. Is this problem $$\mathsf{NP}$$-hard? If not, how can we find such a walk?

• Since this problem is not a decision problem, it is not in $\mathsf{NP}$. Perhaps you want to consider the decision version of the problem? Commented Nov 28, 2021 at 9:16
• I apologize, the mistake was corrected. Commented Nov 28, 2021 at 9:25
• The shortest walk from $u$ to $v$ via $w$ consists of a shortest walk from $u$ to $w$ together with a shortest walk from $w$ to $v$. Commented Nov 28, 2021 at 15:31
• If we choose a bit longer walk from u to w, then, might we can use the lightened edges more efficiently. So I think that the greedy algorithm can not find an optimal walk. Commented Nov 28, 2021 at 19:49
• cs.stackexchange.com/q/146174/755
– D.W.
Commented Nov 29, 2021 at 0:24

The shortest walk must have the form

u
\
t<->w
/
v


where the edges in each arrow are disjoint. To see this, suppose in the shortest walk, we go through nodes $$u_1'=u,\ldots,u_{k'}',u_1,\ldots,u_k=w$$ from $$u$$ to $$w$$, go through nodes $$v_1=w,\ldots,v_l,v_1',\ldots,v_{l'}'=v$$ from $$w$$ to $$v$$, where $$v_1',\ldots,v_{l'}' \notin \{u_1',\ldots,u_{k'}',u_1,\ldots,u_k\}$$, and $$v_l=u_1$$, like the following graph:

                  u    (u_1,...,u_k)
(u_1',...,u_{k'}')\        /\
u_1(v_l)  w       The walk (u_1,...,u_k) may overlap with (v_1,...,v_l)
(v_1',...,v_{l'}')/        \/
v    (v_1,...,v_l)


Now suppose edges $$e_1,\ldots,e_h$$ are shown in both the walk $$(u_1,...,u_k)$$ and the walk $$(v_1,\ldots,v_l)$$, and the remaining edges in both walks are $$f_1,\ldots,f_p$$ and $$g_1,\ldots,g_q$$ respectively. Then the cost of the walk $$(u_1,...,u_k=v_1,\ldots,v_l)$$ is \begin{align*} &\sum_{i=1}^h (W_1(e_i)+W_2(e_i))+\sum_{i=1}^pW_1(f_i)+\sum_{i=1}^qW_1(g_i)\\ \ge{}&\sum_{i=1}^h (W_1(e_i)+W_2(e_i))+\frac{1}{2}\left(\sum_{i=1}^p(W_1(f_i)+W_2(f_i))+\sum_{i=1}^q(W_1(g_i)+W_2(g_i))\right). \end{align*} That is, the average cost of the walk $$(u_1,\ldots,u_k,\ldots,u_1)$$ and the walk $$(v_l,\ldots,v_1,\ldots,v_l)$$ is no more than that of the walk $$(u_1,...,u_k=v_1,\ldots,v_l)$$. So the shortest walk must have the form shown in the first figure.

Now you can try every node as $$t$$ to compute the optimal walk from $$u$$ to $$w$$ to $$v$$. This is a polynomial-time algorithm.