Solution Approaches for the Elementary Shortest Path Problem

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 the paths with minimum cost from a source node to each other node, that do not contain repeated nodes. Three different solution strategies are proposed to solve the problem under investigation and their theoretical proper-ties 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. The last solution strategy is an enumerative approach based on a tree structure, constructed with a cycle elimination rule. Theoret-ical aspects related to the innovative proposed strategies to solve the problem at hand are investigated. The practical behaviour of the defined algorithms is also evaluated by considering a meaningful number of test problems