  A shortest-path algorithm finds a path containing the minimal cost between
two vertices in a graph. A plethora of shortest-path algorithms is studied in
the literature that span across multiple disciplines. This paper presents a
survey of shortest-path algorithms based on a taxonomy that is introduced in
the paper. One dimension of this taxonomy is the various flavors of the
shortest-path problem. There is no one general algorithm that is capable of
solving all variants of the shortest-path problem due to the space and time
complexities associated with each algorithm. Other important dimensions of the
taxonomy include whether the shortest-path algorithm operates over a static or
a dynamic graph, whether the shortest-path algorithm produces exact or
approximate answers, and whether the objective of the shortest-path algorithm
is to achieve time-dependence or is to only be goal directed. This survey
studies and classifies shortest-path algorithms according to the proposed
taxonomy. The survey also presents the challenges and proposed solutions
associated with each category in the taxonomy.

Data Structures and Algorithms