Pengukuran Beban Komputasi Algoritma Dijkstra, A*, dan Floyd-Warshall pada Perangkat Android
Abstract
Perkembangan teknologi di bidang komunikasi menciptakan berbagai kemudahan bagi pengguna untuk melakukan pertukaran informasi tanpa mengenal jarak secara geografis. Pada jaringan komunikasi, pertukaran informasi memerlukan pengaturan rute sehingga dicapai jalur terpendek untuk mengoptimalkan proses pengiriman data. Penelitian untuk mencari algoritma jalur terpendek masih terus dilakukan. Penelitian ini membandingkan algoritma Dijkstra, A*, dan Floyd-Warshall dari sisi waktu, beban komputasi dan penggunaan memori. Topologi yang digunakan dalam penelitian adalah topologi jaringan mesh karena dapat mewakili kondisi nyata. Aplikasi berbasis Android dapat digunakan sebagai simulator untuk memetakan vertice dan edge ke dalam kumpulan node dan channel yang saling berhubungan. Kompleksitas komputasi dalam pencarian jalur terpendek menjadi hal yang penting karena terdapat keterbatasan prosesor dan memori. Kompleksitas rute akan sebanding dengan skala jaringan mesh. Dari simulasi diperoleh nilai beban komputasi dan waktu simulasi yang sebanding dengan fungsi kuadrat jumlah simpul untuk ketiga algoritma tersebut. Hasil pengujian menunjukkan algoritma A* memiliki beban komputasi dan waktu simulasi yang paling kecil dibandingkan algoritma Dijkstra dan Floyd-Warshall tanpa mempengaruhi hasil pencarian rute terpendek. Hal ini disebabkan algoritma A* melakukan operasi pencarian dengan memanfaatkan nilai heuristik terhadap simpul tujuan, sehingga tidak semua simpul dilakukan pengecekan. Namun algoritma Dijkstra paling unggul dalam penggunaan memori. Floyd-Warshall menghasilkan nilai kompleksitas yang buruk pada proses pancarian jalur, semua data bobot kanal akan ditampung ke dalam matriks dua dimensi lalu diproses menggunakan operasi perulangan yang bertingkat.
Kata kunci - shortestpath, djikstra, a*, floyd-warshall, weighted graph, mesh, android
Downloads
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution-ShareAlike International License (CC-BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
Copyright without Restrictions
The journal allows the author(s) to hold the copyright without restrictions and will retain publishing rights without restrictions.
The submitted papers are assumed to contain no proprietary material unprotected by patent or patent application; responsibility for technical content and for protection of proprietary material rests solely with the author(s) and their organizations and is not the responsibility of the ULTIMA Computing or its Editorial Staff. The main (first/corresponding) author is responsible for ensuring that the article has been seen and approved by all the other authors. It is the responsibility of the author to obtain all necessary copyright release permissions for the use of any copyrighted materials in the manuscript prior to the submission.
