Lower Bounds for Relaxation-Based Shortest Path Algorithms Open Access

Abstract

Computing shortest paths in directed, weighted graphs is a classical algorithms problem with applications to transportation, social networking, and many other fields. Although recent years have seen the development of fast shortest path procedures, the traditional Bellman-Ford algorithm and others like it remain the only shortest path algorithms that can operate on a general graph and therefore still see use in fields like packet routing. This paper examines existing lower bounds for the performance of Bellman-Ford-like shortest path algorithms. It moves beyond the non-adaptive setting that has received frequent attention to examine adaptive algorithms, which are attentive to information beyond the mere topology of the input graph. Specifically, I will expand some existing results about non-adaptive algorithms to a more general set of non-adaptive and weakly adaptive approaches. Additionally, I will produce new lower bounds for several Bellman-Ford-like adaptive algorithms that show the inclusion of adaptive heuristics does not improve the minimum number of relaxation operations beyond n-cubed on a weighted graph with n vertices.

Table of Contents

1 Introduction

2 Definitions

3 Related Work

3.1 The Supersequence Problem

3.2 Existing Upper Bounds

3.2.1 Yen's Algorithm

3.2.2 Randomized Approaches

3.2.3 Related Problems

3.3 Existing Lower Bounds

3.3.1 Non-Adaptive Deterministic Algorithms

3.3.2 Non-Adaptive Randomized Algorithms

3.3.3 Stochastic Algorithms

3.3.4 Hardness of Bellman-Ford

4 Our Results

4.1 Improving Existing Results

4.1.1 Meyer e al.

4.1.2 Eppstein

4.2 New Results

4.2.1 Problem Statement

4.2.2 Deterministic Weakly Adaptive Algorithms

4.2.3 Removing Assumptions

4.2.4 Randomized Weakly Adaptive Algorithms

5 Conclusion

Bibliography

About this Honors Thesis

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Emory College
Department	Computer Science
Degree	B.S.
Submission	Honors Thesis
Language	English
Research Field	Computer Science Mathematics
Keyword	Bellman-Ford Computer Science Mathematics Shortest Path Asymptotic Algorithms
Committee Chair / Thesis Advisor	Grigni, Michelangelo, Emory University
Committee Members	Weissman, Daniel, Emory University Ettinger, Bree, Emory University

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Lower Bounds for Relaxation-Based Shortest Path Algorithms ()	2024-04-04 18:02:19 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions