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 Ti ÇTj = Æ, " i, j=1,¼,N, i ¹ j{T_i cap T_j = emptyset, forall i, j=1,ldots,N, i neq 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.
展开▼
机译：最短路径巡回问题（SPTP）包括在有向图中以非负弧长找到从给定的始发节点s到给定的目标节点d的最短路径，并具有以下约束：最优路径P应至少连续且顺序地通过给定节点子集T 1 ，T 2 ，...中的一个节点。 。 。 ，T N ，其中T i ÇT j =Æ，“ i，j = 1，¼，N，i¹j {T_i cap T_j = emptyset，forall i，j = 1，ldots，N，i neq j}。本文将证明SPTP属于复杂度类P，并将提出几种替代技术来解决它。
展开▼
