This chapter is from the book
This chapter is from the book
This chapter is from the book
Table 21.4 summarizes the algorithms that we have discussed in this chapter and gives their worst-case performance characteristics. These algorithms are broadly applicable because, as discussed in Section 21.6, shortest-paths 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 shortest-paths algorithms
|
This table summarizes the cost (worst-case running time) of various shortest-paths algorithms considered in this chapter. The worst-case 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 |
|
single-source |
|||
|
nonnegative |
Dijkstra |
V2 |
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 |
? |
NP-hard |
|
all-pairs |
|||
|
nonnegative |
Floyd |
V3 |
same for all networks |
|
nonnegative |
Dijkstra (PFS) |
VE lg V |
conservative bound |
|
acyclic |
DFS |
VE |
same for all networks |
|
no negative cycles |
Floyd |
V3 |
same for all networks |
|
no negative cycles |
Johnson |
VE lg V |
conservative bound |
|
none |
open |
? |
NP-hard |
On the one hand, the general problem of finding shortest paths in networks where edge weights could be negative is intractable. Shortest-paths 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 shortest-paths 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 single-source problem in networks that contain no negative cycles and for the all-pairs 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 shortest-paths 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 Sections 21.2 through 21.4; if we cannot make such a guarantee, we have to use the algorithms from Section 21.7. Encapsulating these considerations in an ADT is easily done and expands the utility of the algorithms.
Shortest-paths problems put us at a crossroads between elementary graph-processing 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 network-flow 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 NP-hard 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 shortest-paths problems. As we address more difficult problems, we draw on classical methods from both fields of research.