Shortest path methods: A unifying approach. (English) Zbl 0605.90123

Gallo, Giorgio; Pallottino, Stefano

Math. Program. Study 26, 38-64 (1986).

This paper gives a review of algorithms for the problem of finding shortest paths in a directed graph with given arc lengths. Firstly, the problem of finding shortest paths from a given origin node to all other nodes of the graph is considered. A general algorithm is outlined in which nodes of the graph are assigned labels that are successively updated until they are guaranteed to represent the required shortest path lengths. At each iteration updating is performed by selecting a label for some node which is used in conjunction with the lengths of arcs directed from that node. It is shown that all well-known algorithms are obtained from this general method by specifying a selection rule for the label and choosing an appropriate data structure. Algorithms are classified as to whether or not the selection rule searches for a smallest label. A detailed discussion of the various possibilities for selection rules and data structures is given and in each case the computational complexity of the resulting algorithm is derived. Also, a report on the computational performance of the algorithms for large sparse graphs is given. The paper also reviews reoptimization methods which are used when the solution of an almost identical shortest path problem is known. Lastly, algorithms for findig a shortest path between all pairs of nodes are described. These may either use a direct approach or, to save on storage requirements, they can use a sequential approach in which each node is taken in turn as the origin. In the sequential approach the use of reoptimization methods is often advantageous.

Reviewer: Ch.N.Potts

MSC:

90C35	Programming involving graphs or networks
90C10	Integer programming
65K05	Numerical mathematical programming methods
90B10	Deterministic network models in operations research
90C27	Combinatorial optimization

Keywords:

shortest paths in a directed graph; given arc lengths; selection rule; computational performance; large sparse graphs; reoptimization