Destinasi wisata di Kalimantan Selatan memiliki potensi yang besar untuk dikembangkan, namun masih menghadapi tantangan dalam hal aksesibilitas dan efisiensi perjalanan antar lokasi wisata. Kondisi ini menimbulkan kebutuhan sistem navigasi yang mampu membantu wisatawan menemukan rute perjalanan yang lebih cepat dan efektif. Penelitian ini bertujuan untuk menentukan rute terpendek destinasi wisata di Kalimantan Selatan dengan menerapkan algoritma A-Star. Sebanyak 26 titik wisata yang tersebar di berbagai kabupaten dan kota di Kalimantan Selatan dimodelkan dalam bentuk graf. Graf yang telah diproyeksikan digunakan untuk menghitung jalur optimal dengan pendekatan heuristik berdasarkan Algoritma A-Star. Algoritma ini mampu menyeleksi urutan kunjungan wisata secara efisien. Hasilnya menunjukkan bahwa metode ini menghasilkan rute yang lebih optimal dan menghemat waktu dalam penyeleksian rute. Penelitian ini diharapkan dapat berkontribusi pada pengembangan sistem navigasi wisata yang lebih efisien dan dapat mendukung promosi pariwisata lokal secara digital.