On the shortest path problem with negative cost cycles

In this paper, the elementary single-source all-destinations shortest path problem is considered. Given a directed graph, containing negative cost cycles, the aim is to find paths with minimum cost from a source node to each other node, that do not contain repeated nodes. Two solution strategies are proposed to solve the problem under investigation and their theoretical properties are investigated. The first is a dynamic programming approach, the second method is based on the solution of the k shortest paths problem, where k is considered as a variable. Theoretical aspects related to the innovative proposed strategies to solve the problem at hand are investigated. The practical behaviour of the defined algorithms is evaluated by considering random generated networks and instances derived from vehicle routing benchmark test problems.