Analysis of Bus Routes in Phra Nakhon Si Ayutthaya Province with Dijkstra’s Algorithm

Abstract

Dijkstra's algorithm was invented to find the shortest path from one vertex to any vertex in the weighted graph. This research aims to study the routes of buses traveling between districts in Phra Nakhon Si Ayutthaya Province to provide the information for those traveling who want to consider the length of time used and travel expenses. By considering the problem in the form of a weighted graph, vertices in the graph represent the main pick-up points in each district. Phra Nakhon Si Ayutthaya Province has a total of 16 districts, with some districts having more than one main pick-up point. The total of 22 points of a graph was obtained. The edges in the graph represent the routes of buses traveling between districts. The obtained graph is considered in the form of two weighted graphs: the first graph is the weight of the time spent traveling on each route, taken from Google map. The second graph is the weight of the fare for each route, which was obtained by asking the information from drivers and passengers. After that, simple graph emerged by combining both graphs. For routes with more than one travel option in both graphs, only the route with the least weight will be considered by applying the Dijkstra’s algorithm on both graphs. The data obtained from the first graph show the shortest route that takes the shortest duration to travel from Phra Nakhon Si Ayutthaya District to all main pick-up point of other districts. The results of the second graph indicate  the route with the lowest cost from Phra Nakhon Si Ayutthaya District to all main pick-up point of other districts.