MURAL - Maynooth University Research Archive Library



    Shortest Path Computation: A Comparative Analysis


    Sherlock, Ross and Mooney, Peter and Winstanley, Adam C. and Husdal, Jan (2002) Shortest Path Computation: A Comparative Analysis. In: GIS Research UK, April 2002, Sheffield.

    [img]
    Preview
    Download (20kB) | Preview


    Share your research

    Twitter Facebook LinkedIn GooglePlus Email more...



    Add this article to your Mendeley library


    Abstract

    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.

    Item Type: Conference or Workshop Item (Paper)
    Keywords: Shortest Path Computation; ArcView; Java; C++;
    Academic Unit: Faculty of Science and Engineering > Computer Science
    Item ID: 4913
    Depositing User: Dr. Adam Winstanley
    Date Deposited: 25 Apr 2014 15:37
    Refereed: No
    URI:

      Repository Staff Only(login required)

      View Item Item control page

      Downloads

      Downloads per month over past year