Minimum path between two vertices passing through a given set exactly once Suppose I have a source node $S$, destination node $D$ and a set $A$ of intermediate nodes $P_1, P_2, \dots$ in an edge-weighted undirected graph. I want to find the vertex $P_i\in A$ that minimizes $\mathrm{dist}(S, P_i) + \mathrm{dist}(D, P_i)$?  In addition, the overall path from $S$ to $D$ should contain only one node from the set $A$.  What is an efficient algorithm for this? I don't want to go with brute-force approach.
The following answers the variant which requires passing through the set exactly once.

Make two copies of the graph. Remove all edges incident to two vertices of $A$. Orient all edges incident to $A$ in the first copy toward $A$, and all edges incident to $A$ in the second copy from $A$; other edges are bidirectional. Connect both copies of each vertex in $A$ with a zero-weight edge going from the first copy to the second copy. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

Using Dijkstra's algorithm, the complexity of this approach is $O(E+V\log V)$. In comparison, the trivial algorithm that tests all vertices in $|A|$ one at a time needs to run Dijkstra's algorithm $|A|$ times, unless the graph is unweighted, in which case one can use BFS instead in time $O(E|A|)$.



Here is an alternative solution, using only undirected graphs. Start by deleting all edges inside $A$. Add $M$ to the weight of all other edges incident to $A$, where $M$ is larger than the sum of all weights in the graph. Run Dijkstra's algorithm twice to find the shortest path between $S$ and any vertex in $A$, and between $T$ and any vertex in $A$; in both cases, the shortest path passes through no other vertex in $A$, due to our adjustment of the weights. Now go over all vertices $A$ and find the shortest path from $S$ to $T$ via a vertex in $A$.

This algorithm also runs in time $O(E+V\log V)$.



The following answers the variant which requires passing through the set at least once.

Make two copies of the graph. Connect both copies of each vertex in $A$ with an edge of zero weight. Now look for a shortest path between the first copy of $S$ and the second copy of $T$.

The complexity is $O(E+V\log V)$, or $O(E+V)$ if the original graph is unweighted (in this case, we modify the construction so that the parallel $A$-edges have unit weight; this is harmless in terms of computing the shortest path).