Find the shortest path in a graph which must pass certain nodes.

Question

I have a directed weighted graph with 16 vertices. One node (bottom left side) is labeled "S" as the starting point, the objective is to find the shortest path that passes through all the "must pass" nodes. Below is the graph, and the colored vertices are the "must pass" nodes. Do you have any theorems and algorithms that I can use? Im thinking about Dijkstra Algorithm, but my goal is to find the shortest path that includes those must pass nodes.

Answer 1

You can solve the problem via a combination of two algorithms. First, compute all-pairs shortest path distances between the seven special nodes ($S$ and the colored nodes) in the original directed graph. This step yields $7(7-1)=42$ distances. Now replace all distances to $S$ with $0$, and solve an asymmetric traveling salesman problem in a complete directed graph on the seven nodes, using the distances just obtained. To recover the desired shortest path in the original graph, replace each arc in the TSP tour (except the arc back to $S$) with a corresponding shortest path in the original graph.

The shortest-path distances are

   E  G  J  K  M  N  S 
E    10 14 18  4  3  0 
G 10     4  8 14  7  0 
J 14  4     4 16 11  0 
K 18  8  4    20 15  0 
M  4 14 16 20     7  0 
N  3  7 11 15  7     0 
S 13 14 18 22 17 16   

An optimal TSP tour (with objective value $39$) is then

S M 17 
M E  4 
E N  3 
N G  7 
G J  4 
J K  4 
K S  0 

Expanding the tour to a shortest path in the original network yields

S B 9 
B E 4 
E M 4 
M E 4 
E N 3 
N O 4 
O G 3 
G J 4 
J K 4 

If you want to avoid repeating $E$, you can replace $M\to E\to N$ with $M\to N$ at the same cost of $7$.