Improving Route-Finding Performance of Dijkstra Algorithm and Maintaining Path Visual Cue Using Douglas-Peucker Algorithm

Smartphones and their mobile applications have become an inseparable part of modern daily life. One of them is a public transportation app that helps people commute with public transportation. Many public transportation service providers have mobile applications as a companion for their customers to improve their quality of service. The application provides useful information and/or important features regarding their service, such as timetables or route finding for public transit. Such features run a slow algorithm to provide real-time or time-based information to the users. Dijkstra is one example of an algorithm that allows users to find the shortest path from one location to another in a public transit network. However, Dijkstra is categorized as a greedy algorithm because it looks at all possible solutions. It takes longer for Dijkstra to find the optimum solution when the number of points in a network graph is high. This study attempted to improve the overall route-finding processing time and reduce the memory footprint while keeping the visual cue of a route path reasonably consistent by utilizing Douglas-Peucker line simplification algorithm to simplify the path and reduce the number of points that Dijkstra algorithm processes. The result suggested that Douglas-Peucker simplification process took 0.5% additional memory footprint and put 5.13% additional processing time into the overall route-finding processing time. However, it reduces the overall memory footprint and processing time by 72.56% and 80.83%, respectively. The result conveyed a significant improvement in the practical implementation of Douglas-Peucker algorithm to reduce the input for the Dijkstra algorithm in finding the optimal route, thereby improving the overall route-finding performance.