Perbandingan Algoritme Dijkstra dan Algoritme A* (A-Star) dalam Penentuan Lintasan Terpendek dari Dinas Pendidikan Provinsi Lampung ke Beberapa Sekolah Menengah Atas (SMA) Negeri di Provinsi Lampung

Abstract

In this research, we aim to find the most efficient route from the Lampung Provincial Education Office to various State Senior High Schools in Lampung Province, employing both the Dijkstra Algorithm and the A* (A-Star) Algorithm. To address this problem, we model it as a weighted graph, where the vertices represent the locations of the Lampung Provincial Education Office and the Public High Schools, and the edges' weights represent the distances. Furthermore, we implement the solution using the Python programming language. The outcomes demonstrate that both algorithms yield optimal results with the same distance and route. However, when considering the execution time of the program, the A* (A-Star) algorithm outperforms Dijkstra's Algorithm because it quickly identifies the shortest path from the starting point to the destination, whereas Dijkstra's Algorithm explores the shortest paths from neighboring points first.