MURAL - Maynooth University Research Archive Library



    Shortest Path Computation: A Comparative Analysis


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

    [thumbnail of AW_Shortest_Path.pdf]
    Preview
    Text
    AW_Shortest_Path.pdf

    Download (20kB) | Preview

    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: https://mural.maynoothuniversity.ie/id/eprint/4913
    Use Licence: This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

    Repository Staff Only (login required)

    Item control page
    Item control page

    Downloads

    Downloads per month over past year

    Origin of downloads