×

A priority queue for the all pairs shortest path problem. (English) Zbl 0539.68022

A linked list priority queue data structure is given that in some situations out performs, in terms of comparisons amongst elements in the data structure, existing priority queue structures such as the heap. It is shown that this new queue structure is suitable for use with E. W. Dijkstra’s shortest path algorithm [Numer. Math. 1, 269-271 (1959; Zbl 0092.160)] with the combination yielding an algorithm for the all pairs shortest path problem that on a dense graph of n vertices requires \(n^ 3+O(n^{2.5})\) operations on path costs. In a computational framework where addition and comparison are the only operations permitted on path costs, this slightly improves J. Y. Yen’s bound [J. Assoc. Comput. Mach. 19, 423-424 (1972; Zbl 0242.94028)] of \((3/2)n^ 3\) operations.

MSC:

68W99 Algorithms in computer science
68P05 Data structures
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Bloniarz, P. A., A shortest path algorithm with expected time \(O(n^2 logn log^∗\) n)\), SIAM J. Comput., 12, 588-600 (1983) · Zbl 0521.68078
[3] Dijkstra, E. W., A note on two problems in connexion with graphs, Numer. Math., 1, 269-271 (1959) · Zbl 0092.16002
[4] Floyd, R. W., Algorithm 97: shortest path, Comm. ACM, 5, 345 (1962)
[5] Fredman, M. L., New bounds on the complexity of the shortest path problem, SIAM J. Comput., 5, 83-89 (1976) · Zbl 0326.68027
[6] Iri, M.; Nakamori, M., Path sets, operator semigroups and shortest path algorithms on a network, RAAG Res. Notes, 185 (1972), Third series · Zbl 0245.05106
[7] Johnson, D. B., Priority queues with update and finding minimum spanning trees, Inform. Process. Lett., 4, 53-57 (1975) · Zbl 0318.68032
[8] Moran, S., A note on ‘Is shortest path problem not harder than matrix multiplication?’, Inform. Process. Lett., 13, 85-86 (1981) · Zbl 0474.68078
[9] Romani, F., Shortest path problem is not harder than matrix multiplication, Inform. Process. Lett., 11, 134-136 (1980) · Zbl 0454.68069
[10] Spira, P. M., A new algorithm for finding all shortest paths in a graph of positive edges in average time \(O(n^2 log^2n)\), SIAM J. Comput., 2, 28-32 (1973) · Zbl 0254.05118
[11] Takaoka, T.; Moffat, A. M., An \(O(n^2\) log \(n\) log log \(n)\) expected time algorithm for the all shortest distance problem, (Lecture Notes in Comput. Sci., 88 (1980), Springer: Springer Berlin), 643-655
[12] Williams, J. W.J., Algorithm 232: heapsort, Comm. ACM, 7, 347-348 (1964)
[13] Yen, J. Y., Finding the lengths of all shortest paths in \(N\)-node nonnegative distance complete networks using \(12N^3 additions and N^3\) comparisons, J. ACM, 19, 423-434 (1972) · Zbl 0242.94028
[14] Yuval, G., An algorithm for findings all the shortest paths using \(N^{2.81}\) infinite precision multiplications, Inform. Process. Lett., 4, 155-156 (1976) · Zbl 0333.68034
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.