### 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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics |

Publisher | Curran Associates Inc. |

Pages | 118-132 |

Number of pages | 15 |

ISBN (Print) | 9780898716535 |

DOIs | |

State | Published - Jan 1 2008 |

Event | 10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08 - San Francisco, CA, United States Duration: Jan 19 2008 → Jan 19 2008 |

### Publication series

Name | Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics |
---|

### Other

Other | 10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08 |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/19/08 → 1/19/08 |

### All Science Journal Classification (ASJC) codes

- Engineering(all)
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Shortest path feasibility algorithms: An experimental evaluation'. Together they form a unique fingerprint.

## Cite this

Cherkassky, B. V., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. (2008). Shortest path feasibility algorithms: An experimental evaluation. In

*Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics*(pp. 118-132). (Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics). Curran Associates Inc.. https://doi.org/10.1137/1.9781611972887.12