Shortest-Path Algorithms

Edith Cohen

ABSTRACT

Finding the shortest path to a destination is a fundamental computational problem. Applications range from ones predating the computer age (geographic route selection) to widely-deployed routing algorithms in modern computer networks (e.g., OSPF routing). Shortest-path computations often arise as subroutines when solving a more complex problem. We survey some classical and more recent work on efficiently computing shortest paths and distances. We list several interesting variants of the problem, sketch algorithms when possible, and refer the reader to the rich literature on the subject.