Shortest path algorithms using dynamic breadth-first search. (English) Zbl 0717.90077
Summary: A new O(nm) label-correcting algorithm is presented for finding shortest paths from a given node to all other nodes in a network of n nodes and m arcs or finding a directed cycle of negative length. In this algorithm, a node is scanned on the k-th scanning step only of its “label depth” - i.e., the length of the path corresponding to the distance label - equals k. Variants of this algorithm are discussed, and computational results show that several of these are very efficient. A new criterion for detecting a negative cycle that is also based on the label depth of a node is given, and computational tests show that it is extremely effective.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
References:
| [1] | Bellman, Q. Appl. Math 16 pp 87– (1958) |
| [2] | Deo, Networks 14 pp 275– (1984) |
| [3] | Desrochers, Operations Res. Lett 6 pp 183– (1987) |
| [4] | Dreyfus, Operations Res. 17 pp 393– (1969) |
| [5] | Networks flow theory. The Rand Corporation (1956) P-923. |
| [6] | and , Flows in Networks. Princeton University Press, Princeton, NJ (1962). |
| [7] | Glover, Operations Res. 33 pp 65– (1985) |
| [8] | Goldfarb, Networks 20 pp 79– (1990) |
| [9] | Goldfarb, Operations Res. 38 pp 624– (1990) |
| [10] | Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976). · Zbl 0413.90040 |
| [11] | The shortest path through a maze. Proceedings of the International Symposium on Theory of Switching, Part II (1957) 285–292. |
| [12] | and , Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ (1982). · Zbl 0503.90060 |
| [13] | Pierce, Networks 5 pp 129– (1975) |
| [14] | Improvements to the theoretical efficiency of the simplex method. Ph.D. Thesis, Carleton University, Ottawa (1981). Dissertation Abstract International 13, 48B. |
| [15] | Yen, Q. Appl. Math. 27 pp 526– (1970) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
