  We consider single-source shortest path algorithms that perform a sequence of
relaxation steps whose ordering depends only on the input graph structure and
not on its weights or the results of prior steps. Each step examines one edge
of the graph, and replaces the tentative distance to the endpoint of the edge
by its minimum with the tentative distance to the start of the edge, plus the
edge length. As we prove, among such algorithms, the Bellman-Ford algorithm has
optimal complexity for dense graphs and near-optimal complexity for sparse
graphs, as a function of the number of edges and vertices in the given graph.
Our analysis holds both for deterministic algorithms and for randomized
algorithms that find shortest path distances with high probability.
