Complexity analysis and optimization of the shortest path tour problem

The shortest path tour problem (SPTP) consists in finding a shortest path from a given origination node s to a given destination node d in a directed graph with nonnegative arc lengths with the constraint that the optimal path P should successively and sequentially pass through at least one node from given node subsets T 1, T 2, . . . , T N , where $T_i\cap T_j=\varnothing ,\forall i,j=1,\dots ,N,i\ne j$ . In this paper, it will proved that the SPTP belongs to the complexity class P and several alternative techniques will be presented to solve it.