Name
Abstract | ||
|---|---|---|
In application areas such as geographical information systems, the Euclidean metric is often less meaningfully applied to determine a shortest path than metrics which capture, through weights, the varying nature of the terrain (e.g., water, rock, forest). Considering weighted metrics, however, increases the run-time of algorithms considerably suggesting the use of a parallel approach. In this paper, we provide a parallel implementation of shortest path algorithms for the Euclidean and weighted metrics on triangular irregular networks (i.e., a triangulated point set in which each point has an associated height value). To the best of our knowledge, this is the first parallel implementation of shortest path problems in these metrics. We provide a detailed discussion of the algorithmic issues and the factors related to data, machine, implementation which determine the performance of parallel shortest path algorithms. We describe our parallel algorithm for weighted shortest paths, its implementation and performance for single-and multiple-source instances. Our experiments were performed on standard architectures with different communication/computation characteristics, including PCs interconnected by a cross-bar switch using fast ethernet, a state-of-the-art Beowulf cluster with gigabit interconnect and a shared-memory architecture, SunFire. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/j.parco.2003.05.004 | Parallel Computing |
Keywords | Field | DocType |
parallel algorithm,weighted metrics,shortest path algorithm,shortest path problem,parallel implementation,domain (data) partitioning,shortest path,tin processing,parallel approach,euclidean metric,parallel computing,weighted shortest path,shortest paths,geometric shortest path algorithm,parallel shortest path algorithm,gis,parallel computer,triangular irregular network,shared memory | Shortest path problem,Computer science,Parallel algorithm,Parallel computing,Euclidean distance,Constrained Shortest Path First,Theoretical computer science,Yen's algorithm,Shortest Path Faster Algorithm,K shortest path routing,Distributed computing,Euclidean shortest path | Journal |
Volume | Issue | ISSN |
29 | 10 | Parallel Computing |
Citations | PageRank | References |
14 | 0.76 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Lanthier | 1 | 168 | 11.84 |
| Doron Nussbaum | 2 | 89 | 13.49 |
| Jörg-Rüdiger Sack | 3 | 1099 | 166.07 |