  All traditional methods of computing shortest paths depend upon
edge-relaxation where the cost of reaching a vertex from a source vertex is
possibly decreased if that edge is used. We introduce a method which maintains
lower bounds as well as upper bounds for reaching a vertex. This method enables
one to find the optimal cost for multiple vertices in one iteration and thereby
reduces the sequential bottleneck in Dijkstra's algorithm.
  We present four algorithms in this paper --- $SP_1$, $SP_2$, $SP_3$ and
$SP_4$. $SP_1$ and $SP_2$ reduce the number of heap operations in Dijkstra's
algorithm. For directed acyclic graphs, or directed unweighted graphs they have
the optimal complexity of $O(e)$ where $e$ is the number of edges in the graph
which is better than that of Dijkstra's algorithm. For general graphs, their
worst case complexity matches that of Dijkstra's algorithm for a sequential
implementation but allows for greater parallelism. Algorithms $SP_3$ and $SP_4$
allow for even more parallelism but with higher work complexity. Algorithm
$SP_3$ requires $O(n + e(\max(\log n, \Delta)))$ work where $n$ is the number
of vertices and $\Delta$ is the maximum in-degree of a node. Algorithm $SP_4$
has the most parallelism. It requires $O(ne)$ work. These algorithms generalize
the work by Crauser, Mehlhorn, Meyer, and Sanders on parallelizing Dijkstra's
algorithm.
