Abstrak— Transportasi pasien antar rumah sakit
membutuhkan jalur tercepat, rute terpendek merupakan salah
satu opsi terbaik. Pencarian jalur terpendek merupakan proses
pencarian menuju simpul tujuan dengan bobot seoptimal
mungkin, bobot yang digunakan berupa jarak tempuh. Jarak
didapat dari proses perhitungan menggunakan rumus Haversine.
Algoritma ¬Floyd-Warshall dan A*(star) merupakan algoritma
pencarian yang dapat digunakan untuk mencari jalur terpendek.
Dari perhitungan menggunakan algoritma Floyd-Warshall
didapat jarak dan simpul antar rumah sakit Samarinda Medika
Citra menuju rumah sakit umum daerah Abdul Wahab
Sjahranie melalui 12 simpul dengan jarak heuristik 2,987
kilometer, dan dari rumah sakit Dirgahayu menuju rumah sakit
umum daerah Abdul Wahab Sjahranie melalui 11 simpul dengan
jarak heuristik 3,764 kilometer. Hasil menggunakan algoritma
A*(star) diperoleh jarak heuristik 4,733 kilometer dari rumah
sakit Samarinda Medika Citra menuju rumah sakit umum
daerah Abdul Wahab Sjahranie melalui 15 simpul, dan dari
rumah sakit Dirgahayu menuju rumah sakit umum daerah
Abdul Wahab Sjahranie melalui 18 simpul dengan jarak
heuristik 10,607 kilometer.