Desain dan Analisis Algoritma Dijkstra dan Metode Visibility Graph Naive untuk Penyelesaian Persoalan Spoj The Archipelago

Abstract

Permasalahan pada SPOJ 780 The Archipelago adalah sebagai berikut. Diberikan sekumpulan pulau yang memiliki beberapa terminal dan area terlarang yang tidak boleh dilewati selama jalur darat di pulau tersebut. Kemudian, dicari kemungkinan rute terpendek yang menghubungkan terminal di suatu pulau ke terminal di pulau yang lain, tanpa melewati area terlarang manapun, dan total jarak pada 1 pulau harus dibulatkan ke atas. Untuk menyelesaikan permasalahan tersebut, dibutuhkan algoritma Visibility Graph Navie, untuk mengetahui titik-titik mana saja yang dapat dilalui, dan algoritma Dijkstra untuk mengetahui rute terpendeknya. Selain itu, juga dilakukan beberapa optimasi untuk mempercepat kinerja sistem, yaitu dengan cara penyederhanaan penggambaran entitas halangan, pengurangan jumlah vertex yang harus dicek visibilitasnya, dan penggunaan backtracking dari vertex tujuan hingga vertex sumber untuk mengetahui total jarak pada tiap pulau. Cara kerja dari sistem adalah sebagai berikut. Diberikan masukan sesuai deskripsi permasalahan. Setelah masukan berhasil diolah, sistem akan memanggil algoritma Dijkstra. Pada tiap current vertex yang dihasilkan di dalam Dijkstra, sistem akan memanggil algoritma Visibility Graph Naive, untuk mengecek visibilitas dari vertex tersebut dengan vertex lain yang se-pulau, agar dapat diketahui vertex mana saja yang menjadi tetangganya. Dijkstra akan berhenti saat current vertex merupakan vertex tujuan. Kemudian saat Dijkstra telah berhenti, sistem akan menghitung total jarak pada tiap pulau, total jarak keseluruhan, dan menyimpan posisi yang dipilih pada rute terpendek. Hasil akhir menunjukkan bahwa sistem dapat berjalan cukup cepat berkat optimasi yang baik, dengan waktu rata-rata sebesar 0.2763 detik dan memori rata-rata 10.533 MB.