Shortest-Path Feasibility Algorithms: An Experimental Evaluation

Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, and Renato F. Werneck

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 new algorithms) has very robust performance in practice. Our work advances the state of the art in the area.

Details

Publication typeArticle
Published inACM Journal of Experimental Algorithmics
URLhttp://doi.acm.org/10.1145/1498698.1537602
Pages2.7:1-2.7:37
Volume14
Number2
PublisherAssociation for Computing Machinery, Inc.
> Publications > Shortest-Path Feasibility Algorithms: An Experimental Evaluation