Algoritma A*(Star) merupakan algoritma best-first search yang dapat menyelesaikan pencarian rute terpendek dengan waktu yang lebih cepat tetapi tidak selalu memberikan solusi optimal. Sedangkan algoritma Dijkstra dapat menyelesaikan pencarian rute terpendek yang menghasilkan solusi optimal dengan waktu pencarian lebih lama. Dengan melihat kelebihan dan kekurangan algoritma Dijkstra dan algoritma A*(Star), penulis membandingkan dua algoritma untuk menunjukkan solusi optimal dengan studi kasus Agen gas LPG Kota Pekanbaru. Hasil dari perbandingan kedua algoritma terdapat beberapa perbedaan rute terpendek dari kedua algoritma dikarenakan algoritma A*(Star) hanya mencari rute berdasarkan nilai heuristic yang paling optimal sedangkan Dijkstra mencari semua node yang tersedia.