I believe this problem to be NP-Complete, but I'm unable to find any references on possible reductions. Given a weighted graph (either undirected or directed, I cannot find results for either but am interested in both), and vertices s, t, u, find the shortest path from s to t which includes u. To clarify, the path should NOT repeat edges. Hence simply combining the shortest s-u and u-t paths is not valid.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It is NP-complete for directed graphs. Even deciding if there exist a path from $s$ to $t$ using vertex $u$ is NP-complete.
The 2-node disjoint path problem is NP-hard for directed graphs$^1$.
We can reduce this problem to your problem: Split each vertex of $G$, so each vertex $v$ in $G$ become $v^-$ and $v^+$, and edge $uv$ become $u^+v^-$, also there are edges $v^-v^+$. Add one new vertex $u$, and edges $t_1^+u$ and $us_2^-$. Let this graph be $G'$.
There exist a path from $s_1^-$ to $t_2^+$ in $G'$ that uses $u$ if and only if there exist a node disjoint path between $(s_1,t_1)$ and $(s_2,t_2)$ in $G$.
As Chao mentioned, the directed case is known to be NP-hard even for unweighted graphs. That said, the problem is fixed parameter tractable with respect to the path length.
For undirected graphs, you can solve the weighted version of the problem, deterministically, in $O(|E|^2 \log|E|)$ using minimum cost flow.