Advanced Search

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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]