ISSN:
1573-2894
Keywords:
Shortest-paths
;
parallel algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract 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 Dial et al., 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01299142
Permalink
