In this paper we give a very simple fully polynomial approximation scheme for the restricted shortest path problem. The complexity of this ϵ-approximation scheme is O(|E|n(log log n + 1/ϵ)), which improves Hassin's original result by a factor of n. Furthermore, this complexity bound is valid for any graph, regardless of the cost values. This generalizes Hassin's results which apply only to acyclic graphs. Our algorithm is based on Hassin's original result with two improvements. First we modify Hassin's result and achieve time complexity of O(|E|n(log log(UB/LB) + 1/ϵ)), where UB and LB are upper and lower bounds for the problem. This modified version can be applied to general graphs with any cost values. Then we combine it with our second contribution, which shows how to find an upper and a lower bound such that UB/LB ⩽ n, to obtain the claimed result.
