A Web Application for Typical Shortest Path of Roads Networks Based on an Improved Dijkstra Algorithm

Abstract

Google Map is one of the most common applications which have been used for calculating distance and time between one point, as a source, and another, as a destination, within specific roads networks. This application often uses a heuristic function to find the shortest path between two points. This function is stopped if the shortest path has been found within a specific area of roads map. In fact, there is no guarantee that the result path is the shortest one ever. This paper presents a novel web application for calculating the typical shortest path between two points of roads networks within a specific area. The application reads an extracting map from Google application and calculates and reduces the searching time by displaying the overall an analytic information of the source and destination point including the explanation if that path is a part of the pervious solution path or not. The application adopts the improved of Dijkstra algorithm which has been developed by emerging a perfect data structure within it. The data structure, which is an array list of linked hash map, is used as storage for solution path. The result shows that the searching time for an ideal shortest path is reduced comparing with the original Dijkstra algorithm if the path is an implicit path.  We believe that our application provides researchers with an accurate analysis of different time spent in the search and gives valuable results of the shortest route between any two points within roads networks.