I'm trying to implement the Goldberg-Radzik algorithm, which is described in the 1993 paper "A heuristic improvement of the Bellman-Ford algorithm" by Andrew Goldberg and Tomasz Radzik (link: http://www.sciencedirect.com/science/article/pii/089396599390022F).
The algorithm is used to solve the single-source shortest path problem for graphs with arbitrary weights. If the graph contains a negative cycle, it is found sooner than the Bellman-Ford algorithm, which doesn't detect negative cycle until the very end.
The Goldberg-Radzik algorithm scans vertices in topological order: if there is an arc (v, w) that has a negative reduced cost (meaning it gives a shorter path to vertex w), then vertex v should be scanned before vertex w. Arcs that have negative reduced cost together form the admissible graph.
The algorithm starts out by computing the vertices reachable from set "B", which initially contains only the source vertex, in the admissible graph. These reachable vertices together form set "A". Set "A" is then topologically ordered, which may be achieved by a depth-first search. Set "B" is reset to the empty set, and vertices in set "A" are scanned in topological order, and any vertices for which the shortest distance is updated are added to set "B". This procedure is repeated until set "B" is empty.
What I don't understand here, is that there are different ways to interpret this. As a first option, one may determine set A (i.e., the vertices reachable from B) by scanning all vertices in B, and put all vertices with updated distances (that were not in B) into A. This means that in the first pass of the algorithm, only the source's direct successors are added to A.
As a second option, one may start a DFS from some vertex in B, and scan each visited vertex, thus updating the admissible graph. As a result, all vertices that are reachable from the source in this way are added to A during the first pass of the algorithm.
The second option seems to be the one proposed by the authors of the paper in the "Concluding remarks" section, as it gives a more efficient implementation (vertices need to be scanned less often). However, the behaviour one gets is not the same for the two options, as is reported in an experiment reported in "Shortest path algorithms: Theory and experimental evaluation" by Cherkassky et al. in Mathematical Programming 73 (1996) (link: http://link.springer.com/article/10.1007/BF02592101).
Since there does not seem to be much material on this algorithm beyond the 1993 paper, I'm wondering if someone has any experience with it and / or can tell me how to properly implement it.
The best way to understand Goldberg-Radzik algorithm (GoR) and all heuristics for the shortest path problem, is to download it from Goldberg website Check the following link http://www.avglab.com/andrew/soft.html and download SPLIB.