I need to prove/disprove an claim that related to "The longest path problem".
For given directed graph $G(V,E)$ with non negative weight function $w(u,v)$, define $L'(u,v)$ as longest path from $u$ to $v$.
I need prove/disprove that for any given simple path $P(v_1,v_2,\ldots,v_i,\ldots,v_j,\ldots,v_k)$ sub-path $(v_i, v_{i+1}, v_{i+2},\ldots,v_j)$ where $1\le i<j\le k$ is longest simple path from $v_i$ to $v_j$.
In simple words, are the sub-paths of Longest path, are longest path?
What I tried is:
Define path $P(v,\ldots,w,\ldots,z,\ldots,v)$
The longest path is $L'(u,v) = L'(u,w) + L'(w,z) + L'(z,v)$
If $L'(w,z)$ is not the longest path, this means that $L'(u,v)$ is not longest path from $u$ to $v$ $\Longrightarrow$ $L'(w,z)$ is longest path from $w$ to $z$.
Is it corrent prove? I know that for undirected graph this prove is wrong and I have an counterexample.
Thanks.
For simplicity, lets make all weights equal. Now, if you take two consecutive vertices on this longest path, isn't it possible there is a longer path between those two, which cannot be combined with the original longest path?
Here is an example:
$$1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8$$ Add the following arcs: $6 ->9 ->1 -> 10 -> 7$
Which is the longest path? Which is the longest path from $6$ to $7$?