The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm
| Autor: | Jeffery L. Kennington, B. Douglas Stewart, Richard V. Helgason |
|---|---|
| Rok vydání: | 1993 |
| Předmět: |
Mathematical optimization
Control and Optimization Applied Mathematics Parallel algorithm Floyd–Warshall algorithm Computational Mathematics Shortest Path Faster Algorithm Suurballe's algorithm K shortest path routing Online algorithm Algorithm Yen's algorithm Dijkstra's algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Computational Optimization and Applications. 2:47-75 |
| ISSN: | 1573-2894 0926-6003 |
| DOI: | 10.1007/bf01299142 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink