Perspective
Table 21.4 summarizes the algorithms that we have discussed in this chapter and gives their worstcase performance characteristics. These algorithms are broadly applicable because, as discussed in , shortestpaths problems are related to a large number of other problems in a specific technical sense that directly leads to efficient algorithms for solving the entire class, or at least indicates such algorithms exist.
Table 21.4. Costs of shortestpaths algorithms
This table summarizes the cost (worstcase running time) of various shortestpaths algorithms considered in this chapter. The worstcase bounds marked as conservative may not be useful in predicting performance on real networks, particularly the Bellman–Ford algorithm, which typically runs in linear time.

weight constraint

algorithm

cost

comment

singlesource




nonnegative

Dijkstra

V^{2}

optimal (dense networks)

nonnegative

Dijkstra (PFS)

E lg V

conservative bound

acyclic

source queue

E

optimal

no negative cycles

Bellman–Ford

VE

room for improvement?

none

open

?

NPhard

allpairs




nonnegative

Floyd

V^{3}

same for all networks

nonnegative

Dijkstra (PFS)

VE lg V

conservative bound

acyclic

DFS

VE

same for all networks

no negative cycles

Floyd

V^{3}

same for all networks

no negative cycles

Johnson

VE lg V

conservative bound

none

open

?

NPhard

On the one hand, the general problem of finding shortest paths in networks where edge weights could be negative is intractable. Shortestpaths problems are a good illustration of the fine line that often separates intractable problems from easy ones, since we have numerous algorithms to solve the various versions of the problem when we restrict the networks to have positive edge weights or to be acyclic, or even when we restrict to subproblems where there are negative edge weights but no negative cycles. On the other hand, several of the algorithms that we have considered for shortestpaths problems are optimal or nearly so. These algorithms are widely used on a broad variety of practical problems. There still are significant gaps between the best known lower bound and the best known algorithm for the singlesource problem in networks that contain no negative cycles and for the allpairs problem in networks that contain nonnegative weights. The algorithms are all based on a small number of abstract operations and can be cast in a general setting. Specifically, the only operations that we perform on edge weights are addition and comparison: Any setting in which these operations make sense can serve as the platform for shortestpaths algorithms. As we have noted, this point of view unifies our algorithms for computing the transitive closure of digraphs with our algorithms for finding shortest paths in networks. The difficulty presented by negative edge weights corresponds to a monotonicity property on these abstract operations: If we can ensure that the sum of two weights is never less than either of the weights, then we can use the algorithms in s 21.2 through 21.4; if we cannot make such a guarantee, we have to use the algorithms from . Encapsulating these considerations in an ADT is easily done and expands the utility of the algorithms. Shortestpaths problems put us at a crossroads between elementary graphprocessing algorithms and problems that we cannot solve. They are the first of several other classes of problems with a similar character that we consider, including networkflow problems and linear programming. As in shortest paths, there is a fine line between easy and intractable problems in those areas. Not only are numerous efficient algorithms available when various restrictions are appropriate, but also there are numerous opportunities where better algorithms have yet to be invented and numerous occasions where we are faced with the certainty of NPhard problems. Many such problems were studied in detail as OR problems before the advent of computers or computer algorithms. Historically, OR has focused on general mathematical and algorithmic models, whereas computer science has focused on specific algorithmic solutions and basic abstractions that can both admit efficient implementations and help to build general solutions. As models from OR and basic algorithmic abstractions from computer science have both been applied to develop implementations on computers that can solve huge practical problems, the line between OR and computer science has blurred in some areas: For example, researchers in both fields seek efficient solutions to problems such as shortestpaths problems. As we address more difficult problems, we draw on classical methods from both fields of research. 