Page 1 - 285-Article Text-512-1-10-20160610
P. 1
ISSN 2355-3286
Pengukuran Beban Komputasi Algoritma
Dijkstra, A*, dan Floyd-Warshall pada
Perangkat Android
Michael Alexander Djojo, Karyono
Program Studi Sistem Komputer, Universitas Multimedia Nusantara, Tangerang, Indonesia
djojo.alexander@gmail.com, karyono@umn.ac.id
Diterima 2 Mei 2013
Disetujui 15 Mei 2013
Abstrak—Perkembangan teknologi di bidang dipergunakan dalam kebutuhan pencarian jalur
komunikasi menciptakan berbagai kemudahan bagi terpendek. Dijkstra dipergunakan dalam protokol
pengguna untuk melakukan pertukaran informasi tanpa routing Open Shortest Path First (OSPF) dalam
mengenal jarak secara geografis. Pada jaringan komunikasi, menentukan rute terpendek pada proses pencarian
pertukaran informasi memerlukan pengaturan rute sehingga jalur komunikasinya [2]. Algoritma A* dapat
dicapai jalur terpendek untuk mengoptimalkan proses dimanfaatkan untuik menghasilkan perhitungan dan
pengiriman data. Penelitian untuk mencari algoritma pemilihan rute dalam sistem penentuan lokasi dan rute
jalur terpendek masih terus dilakukan. Penelitian ini perjalanan yang dikenal dengan Traffic Navigational
membandingkan algoritma Dijkstra, A*, dan Floyd-Warshall System [3]. Selain itu dalam jaringan komunikasi,
dari sisi waktu, beban komputasi dan penggunaan memori. terdapat perangkat switch yang dapat memanfaatkan
Topologi yang digunakan dalam penelitian adalah topologi algoritma Floyd-Warshall sebagai penentuan jalur
jaringan mesh karena dapat mewakili kondisi nyata. Aplikasi penyebaran informasi [1]. Pada jaringan komunikasi,
berbasis Android dapat digunakan sebagai simulator untuk ketepatan pemilihan rute perpindahan paket data
memetakan vertice dan edge ke dalam kumpulan node dapat menjadi kunci dalam memperoleh optimasi
dan channel yang saling berhubungan. Kompleksitas kecepatan. Penelitian beban komputasi algoritma
komputasi dalam pencarian jalur terpendek menjadi hal yang Dijkstra, A*, dan Floyd-Warshall menggunakan
penting karena terdapat keterbatasan prosesor dan memori. model jaringan mesh dilakukan untuk menemukan
Kompleksitas rute akan sebanding dengan skala jaringan perbandingan dalam implementasinya pada perangkat
mesh. Dari simulasi diperoleh nilai beban komputasi dan seluler berbasis Android.
waktu simulasi yang sebanding dengan fungsi kuadrat jumlah
simpul untuk ketiga algoritma tersebut. Hasil pengujian II. SHORTEST PATH PROBLEM
menunjukkan algoritma A* memiliki beban komputasi dan
waktu simulasi yang paling kecil dibandingkan algoritma Shortest Path Problem dapat didefinisikan untuk
Dijkstra dan Floyd-Warshall tanpa mempengaruhi hasil graf berarah, tanpa arah, atau gabungan. Permasalahan
pencarian rute terpendek. Hal ini disebabkan algoritma A* jalan terpendek yang difinisikan pada penelitian ini
melakukan operasi pencarian dengan memanfaatkan nilai difokuskan pada keadaan topologi jaringan mesh,
heuristik terhadap simpul tujuan, sehingga tidak semua sehingga graf yang digunakan merupakan graf
simpul dilakukan pengecekan. Namun algoritma Dijkstra berarah. Graf berarah mengharuskan simpul untuk
paling unggul dalam penggunaan memori. Floyd-Warshall berturut-turut dihubungkan melalui kanal ke tujuan
menghasilkan nilai kompleksitas yang buruk pada proses yang tepat.
pancarian jalur, semua data bobot kanal akan ditampung A. Dijkstra
ke dalam matriks dua dimensi lalu diproses menggunakan
operasi perulangan yang bertingkat. Metode pelabelan Dijkstra merupakan prosedur
utama dalam algoritma tersebut [1]. Keluaran dari
Kata kunci—shortestpath, dijkstra, a*, floyd-warshall, metode pelabelan berupa rangkaian alur dari simpul
weighted graph, mesh, android sumber ke suatu set simpul lain. Alur keluaran
merupakan jarak terpendek dari simpul sumber yang
dapat ditemukan oleh algoritma.
I. PENDAHULUAN
Shortest Path Problem merupakan salah satu Tiga informasi penting yang diperlukan untuk
masalah optimasi yang hingga saat ini masih terus setiap simpul dalam metode pelabelan diantaranya
dipelajari dengan aplikasi di berbagai bidang 1. label jarak,
[1]. Algoritma Dijkstra, A*, dan Floyd-Warshall
merupakan beberapa algoritma shortest path yang 2. label simpul sebelumnya, dan
ULTIMA Computing, Vol. V, No. 1 | September 2013 13
