Algorithms for Obtaining Shortest Paths Visiting Specified Nodes

Let Γ = [P,V,f] be a directed graph with the set of nodes P = \ n₁ ,n₂ , ⋯ ,nₚ \, the set of arcs V and the length of arcs given by f:V → R (real numbers). Let S ⊆ P - \ n₁ ,nₚ \. Two problems are considered in this paper. One is to find the shortest elementary path from n₁ to nₚ, which is constrained to visit all nodes in S. The other is to find the shortest path (not necessarily elementary) under the same condition. For the former problem, an algorithm based on the dynamic programming and an algorithm based on the branch and bound principle are proposed. The computational results gained for the latter approach indicates that problems with 20 ~ 30 nodes can be solved in at most 10 ~ 20 seconds on the FACOM 230–60 computer. For the latter problem, an algorithm based on the dynamic programming formulation is proposed.