  Utilizing graph algorithms is a common activity in computer science.
Algorithms that perform computations on large graphs are not always efficient.
This work investigates the Single-Source Shortest Path (SSSP) problem, which is
considered to be one of the most important and most studied graph problems.
This thesis contains a review of the SSSP problem in both theory and practice.
In addition, it discusses a new single-source shortest-path algorithm that
achieves the same $O(n \cdot m)$ time bound as the traditional
Bellman-Ford-Moore algorithm but outperforms it and other state-of-the-art
algorithms in practice.
  The work is comprised of three parts. The first discusses some basic
shortest-path and negative-cycle-detection algorithms in literature from the
theoretical and practical point of view. The second contains a discussion of a
new algorithm for the single-source shortest-path problem that outperforms most
state-of-the-art algorithms for several well-known families of graphs. The main
idea behind the proposed algorithm is to select the fewest most-effective
vertices to scan. We also propose a discussion of correctness, termination, and
the proof of the worst-case time bound of the proposed algorithm. This section
also suggests two different implementations for the proposed algorithm, the
first runs faster while the second performs a fewer number of operations.
Finally, an extensive computational study of the different shortest paths
algorithms is conducted. The results are proposed using a new evaluation metric
for shortest-path algorithms. A discussion of outcomes, strengths, and
weaknesses of the various shortest path algorithms are also included in this
work.
