Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.

► The elementary shortest path problem with forbidden paths is addressed. ► A mathematical formulation of the problem is developed. ► A B&B based algorithm and dynamic programming approaches are proposed. ► The B&B approach outperforms the dynamic programming methods on small-size problems. ► The dynamic programming methods behave the best on large-size test problems.