Shortest Path Feasibility Algorithms: An Experimental Evaluation, with B. V. Cherkassky, Loukas Georgiadis, A. V. Goldberg, and R. E. Tarjan. Proceeding of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX 2008), San Francisco, California, 2008. Copyright SIAM.

Abstract: This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area.