Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0776.90083
Helgason, Richard V.; Kennington, Jeffery L.; Stewart, B.Douglas
The one-to-one shortest-path problem: An empirical analysis with the two- tree Dijkstra algorithm.
(English)
[J] Comput. Optim. Appl. 2, No.1, 47-75 (1993). ISSN 0926-6003; ISSN 1573-2894/e

Summary: Four new shortest-path algorithms, two sequential and two parallel, for the source-to-sink shortest-path problem are presented and empirically compared with five algorithms previously discussed in the literature. The new algorithm, S22, combines the highly effective data structure of the S2 algorithm of {\it R. Dial}, {\it F. Glover}, {\it D. Karney} and {\it D. Klingman} [Networks 9, 215-248 (1979; Zbl 0414.68035)] with the idea of simultaneously building shortest-path trees from both source and sink nodes, and was found to be the fastest sequential shortest-path algorithm. The new parallel algorithm, PS22, is based on S22 and is the best of the parallel algorithms. We also present results for three new S22-type shortest-path heuristics. These heuristics find very good (often optimal) paths much faster than the best shortest-path algorithm.
MSC 2000:
*90C35 Network programming
65Y05 Parallel computation (numerical methods)
90-08 Computational methods (optimization)

Keywords: shortest-path algorithms; parallel algorithm; heuristics

Citations: Zbl 0414.68035

Highlights
Master Server