Shortest Path Computation: A Comparative Analysis

Given a network structured data set (N spatially embedded nodes (xi,yj) and M edges, each edge Ek mapped to C edge costs) several software options are available allowing one to compute shortest paths between nodes in this data set. Software options include powerful GIS software engines such as ArcView and MapInfo, high level programming language implementations such as C++, Java or LISP and mathematical software such as Matlab and Mathematica. All software options find the same shortest, optimal, paths given the same input criteria. However one may differentiate between each software option based on the relative importance of a small number of criterion. Evaluation criterion can be summarised as software license cost, implementation time (software development hours), implementation cost, underlying data structures, shortest path query execution time (and hence query response time), etc. Current research work into establishing a performance efficiency hierarchy between Java, C++ and ArcView is described. Experimentation will be performed in order to statistically compare shortest path query execution time, response time and implementation issues of ArcView, C++ and Java performing shortest path computations on identical data sets and identical input parameters. This research will provide useful experimental results to GIS researchers uncertain of which implementation best matches their particular shortest path computation needs.