THE APPLICATION OF SEARCHING THE SHORTEST PATH WITH DIJKSTRA ALGORITHM USING J2SE (Java 2 Standard Edition)
Aditha Citra Prigianti Major of Informatic Technique, Faculty of Industry Technology, Gunadarma University
[email protected] Abstract Path/the shortest path is the minimum path which is needed to achieve a place from a particular place. This application can be used for the driver or delivery service as the searching simulation of optimal distance, to get the efficiency of time, besides that this application can be used by students who want to know the process of learning about dijkstra algorithm which is used to search the shortest path. This application will display the shortest path to get to a point desired by the user. User can be flexible to determine the point and determine the respective segments of each point with a certain quality. Results from this application are that it will display the shortest path from the specified point and also the distance required to reach that point. The purpose of this application is for the optimization of time and path to a point. This application will be created using J2SE (Java 2 Standard Edition) language program.
Abstraksi Lintasan/jalur terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Aplikasi ini dapat digunakan untuk para pengendara atau jasa delivery sebagai simulasi pencarian jarak optimal, sehingga mendapatkan keefisiensian waktu, selain itu aplikasi ini dapat digunakan oleh para pelajar yang ingin mengetahui proses pembelajaran tentang algoritma dijkstra yang digunakan untuk pencarian jalur terpendek. Dalam aplikasi ini akan menampilkan jalur terpendek untuk menuju suatu titik yang diinginkan oleh user. User dapat menentukan titik secara fleksibel dan menentukan ruas masing - masing dari titik tersebut dengan bobot tertentu. Yang dihasilkan dari aplikasi ini adalah akan menampilkan jalur terpendek dari titik yang ditentukan beserta jarak yang dibutuhkan untuk mencapai suatu titik tersebut. Tujuan dari aplikasi ini adalah untuk pengoptimalan waktu dan jalur ke suatu titik. Aplikasi ini akan dibuat dengan menggunakan bahasa pemrograman J2SE (Java 2 Standard Edition).
1
1. Pendahuluan 1.1. Latar Belakang Menghubungkan beberapa kota besar mungkin akan dihubungkan secara langsung dengan jalan tol, namun pada umumnya, seperti pada jalan kereta api, untuk penghematan pembuatan jalan, rel kereta api dibuat tidak langsung dibuat seperti jalan tol yang menghubungkan 2 kota yang cukup jauh secara langsung, namun melalui kota-kota yang berada di antaranya, jadi jalanan ini sekaligus menghubungkan kota-kota yang ada diantara kota asal dan kota tujuan kita. Untuk menentukan jalur mana yang akan dipakai agar efisien maka diperlukan cara untuk mendapatkan jalur terpendek. Karenanya pencarian sebuah jalan dengan jarak minimal sangatlah dibutuhkan khususnya dalam dunia transportasi di dunia. Lintasan/jalur terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Penerapan jalur terpendek adalah pada TSP (Travelling Salesman Problem), yang merupakan persoalan mengunjungi sejumlah kota tepat satu kali dan kembali lagi ke kota asal keberangkatannya. Penulis bermaksud untuk mencari penyelesaian dengan membuat suatu program aplikasi pencarian jalur terpendek dengan algoritma Dijkstra menggunakan bahasa pemrograman J2SE (Java 2 Standard Edition). Kelebihan dari algoritma Dijkstra adalah memerlukan waktu yang relatif lebih sedikit dalam mencari jalur terpendek. Sedangkan alasan penulis memilih bahasa pemrograman J2SE
(Java 2 Standard Edition) untuk pembuatan aplikasi pencarian jalur terpendek ini adalah selain memiliki class library yang lengkap, J2SE adalah bahasa pemrograman berbasis objek yang membuat pemrogram mudah untuk mendesain, membuat, mengembangkan dan mengalokasi kesalahan sebuah program dengan basis Java secara cepat, tepat, mudah dan terorganisir. 1.2. Ruang Lingkup Dalam aplikasi ini, penulis menggunakan algoritma Dijkstra yang memang berguna untuk melakukan pencarian jalur terpendek. Dalam pencarian jalur terpendek ini menggunakan graf, penulis mengasumsikan bahwa graf tersebut adalah lokasi. Dalam aplikasi ini, penulis menampilkan suatu layar yang dapat digunakan untuk menentukan lokasi dan jarak antar lokasi yang diinginkan, selain itu juga terdapat contoh penggunaan graf untuk siapa saja yang ingin mempelajarinya. Hasil dari proses ini adalah jalur terpendek yang dapat dicapai. 2. Tinjauan Pustaka 2.1. Jalur/Lintasan Terpendek Jalur/Lintasan terpendek adalah graf berbobot (weighted graph) atau lintasan yang memiliki total bobot minimum. Contoh aplikasi: Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer. Terdapat beberapa jenis persoalan lintasan terpendek, antara lain:
2
Lintasan terpendek antara dua buah simpul tertentu. Lintasan terpendek antara semua pasangan simpul. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
S := empty set Q := V[G] while Q is not an empty set u := Extract_Min(Q) S := S union {u} for each edge(u,v) outgoing from u if d[u] + w(u,v) < d[v] d[v] := d[u] + w(u,v) previous[v] := u. Dengan suatu tumpukan biner, algoritma akan memerlukan O((E+V)Logv) Waktu, dan Fibonacci Tumpukan meningkatkannya menjadi O(E + Vlogv). Jadi kompleksitas algoritma (running time) dijkstra bernilai O(V*Log V + E).
2.2. Algoritma Dijkstra Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah algoritma dengan prinsip greedy yang memecahkan masalah lintasan terpendek untuk sebuah graf berarah dengan bobot sisi yang tidak negatif. Misalnya, bila simpul dari sebuah graf melambangkan kota - kota dan bobot tiap simpul melambangkan jarak antara kota - kota tersebut, algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Input algoritma ini adalah sebuah graf berarah dan berbobot, G dan sebuah source vertex s dalam G. V adalah himpunan semua simpul dalam graph G. Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞), jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua edge dalam path tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t. Dibawah ini adalah pseudocode algoritma dijkstra : function Dijkstra(G, w, s) for each vertex v in V[G] d[v] := infinity previous[v] := undefined d[s] := 0
2.3. Graf Graf adalah himpunan busur dan simpul yang banyaknya berhingga dan busur - busurnya menghubungkan sebagian atau keseluruhan pasangan dari simpulsimpulnya. Dalam menggambarkan graf, simpul digambarkan dengan lingkaran kecil atau titik tebal dan busur digambarkandengan garis, dan arah panah pada garis melambangkan arah dari garis tersebut. Graf G(V, E) terdiri atas himpunan simpul yang dinyatakan dengan V = {v1,v2, v3, ..., vn} dan himpunan busur yang dinyatakan dengan E = {e1, e2, e3, ..., en} dengan ei = (vi, vj) merupakan busur yang menghubungkan simpul vi dan simpul vj. Busur (i,j) disebut busur berarah jika terdapat suatu aliran dari simpul i menuju ke simpul j. Di dalam situasi yang dinamis, seperti contohnya pada komputer digital, ataupun pada sistem aliran (flow system), konsep graf berarah lebih sering digunakan dibandingkan dengan konsep graf tak berarah. Graf berarah dapat digambar pada suatu bidang rata. Simpul, anggota V, digambarkan
3
sebagai titik. Sedangkan ruas A = (u,v), digambarkan sebagai garis dilengkapi dengan tanda panah mengarah dari simpul u ke simpul v. Simpul u disebut titik pangkal, dan simpul v disebut terminal dari arkus A tersebut. Contoh Graf Berarah : Graf berarah D (V, A) dengan : V mengandung 4 smpul, yaitu : 1, 2, 3 dan 4. A mengandung 7 arkus, yaitu : (1,4), (2,1), (2,1), (2,2), (2,3), (2,4), (4,3).
tersebut dengan menentukkan bobotnya. Dalam proses hasil, user akan mendapatkan jalur terpendek dari banyak jalur yang ada dengan menghitung bobot terendah yang dilakukan oleh sistem. Sistem juga menyediakan contoh dari jalannya aplikasi untuk user yang masih kurang mengerti. Aplikasi ini akan membantu user untuk mencari jalur terpendek menuju ke suatu tempat dari beberapa tempat yang ada. 3.2. Flowchart (Alur Program)
Gambar Contoh Graf Berarah Arkus (2, 2) : gelung / self loop Arkus (2,1) : arkus sejajar / arkus berganda Apabila ruas dan/atau simpul suatu graf berarah menyatakan suatu bobot, maka graf berarah tersebut dinamakan suatu jaringan atau network. Graf semacam itu biasanya digunakan untuk menggambarkan situasi dinamis. 3. Metodologi Penelitian 3.1. Analisis Kebutuhan Sistem Pada analisis kebutuhan sistem ini, penulis menggunakan sistem domain application, yaitu rencana pembuatan sistem. Pembuatan sistem ini dilengkapi dengan tampilan interface yang nantinya digunakan oleh user untuk menjalankan aplikasi, yaitu sebagai berikut : 1. Aplikasi ini adalah suatu program untuk mencari jalur terpendek dengan meletakkan simpul - simpul yang dilakukan oleh user. 2. Dalam proses meletakkan simpul simpul tersebut, user dapat menghubungkan simpul – simpul
Gambar Flowchart (Alur Program) Aplikasi Jalur Terpendek Flowchart diatas merupakan gambaran secara umum bagaimana program berjalan dalam menanggapi input pilihan dari pengguna berupa penekanan salah satu tombol yang ada
4
dengan masing – masing tools tersebut, seperti saat user menginginkan untuk membersihkan layar pada aplikasi yang dibuat, maka perintah itu akan dilaksanakan dengan baik dengan cara menekan salah satu tombol yang diaktifkan untuk perintah tersebut.
mulai dari jalannya aplikasi sampai aplikasi ditutup atau selesai dijalankan. 3.3. Struktur Navigasi Struktur navigasi ini digunakan untuk mempermudah pengguna dalam menggunakan aplikasi, karena berisi urutan – urutan proses yang dapat dikerjakan.
3.5. Validasi Sistem Validasi sistem ini dilakukan dengan memasukkan data kedalam sistem yang sedang berjalan, dengan hasilnya adalah sesuai dengan algoritma yang digunakan. Algorima yang dipakai dalam sistem ini adalah algoritma dijkstra. Selain Algoritma dijkstra juga terdapat algoritma Bellman-Ford untuk memecahkan persoalan jalur terpendek ini, hanya saja algoritma ini digunakan untuk graf berbobot untuk bobot yang dapat bernilai positif dan negatif, sehingga waktu yang diperlukan untuk menuju simpul tujuan lebih lama dibanding algorima dijkstra. Misalkan terdapat sebuah jalur seperti gambar dibawah ini:
Gambar Struktur Navigasi Aplikasi Jalur Terpendek Untuk struktur navigasi pada aplikasi jalur terpendek ini, pertama kali aplikasi dijalankan, maka akan muncul tampilan menu utama, kemudian dari menu utama tersebut dapat menuju ke pilihan ‘Clear’, ‘Process’, ‘Step’, ‘Review’, ‘Example’, ‘Save’, ‘Load’, ‘Help’, dan ‘About’. Jika pengguna memilih salah satu pilihan tersebut, maka akan dijalankan proses dari masing – masing pilihan yang dipilih. Dari masing – masing pilihan tersebut dapat langsung menuju piihan lainnya. Kemudian terdapat pilihan ‘Exit’ yang berarti jika pengguna memilih ‘Exit’, maka akan keluar dari aplikasi.
Gambar Contoh Penerapan Jalur Terpendek Terdapat enam buah simpul disana, yaitu simpul 1, 2, 3, 4, 5, dan 6, dengan bobot yang telah diberikan pada masing – masing simpul yang berdekatan. Dengan algoritma dijkstra ini bobot dari masing – masing simpul yang berdekatan dibandingkan, kemudian dipilih bobot yang terkecil, begitu seterusnya sampai semua bobot dari masing – masing simpul yang berdekatan terproses, dan terdapat simpul yang terpilih yang menentukan
3.4. Verifikasi Sistem Verifikasi sistem ini dilakukan dengan implementasi coding kedalam bahasa pemrograman yang digunakan, yaitu J2SE (Java 2 Standard Edition). Misalnya saja dalam mengaktifkan fungsi tools yang digunakan dalam tampilan aplikasi, yaitu dengan cara memasukkan coding yang berhubungan
5
jalur terpendek. Dari gambar diatas, dapat diuraikan ke dalam tabel dibawah ini : Tabel Hasil Contoh Penerapan Jalur Terpendek Sim Simpul Lintasan Jara pul Tujuan terpendek k asal 1 3 10 13 1 4 25 134 1 2 1 3 4 2 45 1 5 45 15 1 6 tidak ada Untuk pembuktiannya, dapat diterapkan pada aplikasi yang dibuat, sebagai berikut :
kedua simpul tersebut. Aplikasi ini menggunakan algoritma dijkstra dimana proses akan berjalan sampai semua simpul sudah terpilih. Saat terdapat beberapa simpul yang telah dihubungkan dengan ruas yang memiliki bobot, maka algoritma akan menganalisis bobot dari simpul – simpul yang dipilih, kemudian akan dipilih simpul dengan bobot yang terkecil, lalu saat simpul tersebut melalui simpul lainnya, dan mendapatkan bobot yang terkecil berikutnya, maka bobot tersebut akan berubah, yaitu dengan menjumlahkan bobot terkecil sebelumnya dengan bobot terkecil berikutnya. 4.2. Uji Coba Aplikasi Uji Coba aplikasi ini dilakukan untuk membuktikan apakah aplikasi berjalan sesuai dengan tujuan yang diharapkan dengan cara mencoba aplikasi tersebut setelah implementasi coding kedalam bahasa pemrograman yang digunakan telah dilakukan. Tahap awal adalah menjalankan aplikasinya dengan cara melakukan compile pada command prompt¸ yaitu ‘javac menuUtama.java’, setelah berhasil dan tidak ada error, maka jalankan aplikasinya dengan mengetik ‘java menuUtama’, maka akan muncul gambar dibawah ini :
Gambar Hasil Validasi Sistem Pada aplikasi ini, dimisalkan simpul 1, 2, 3, 4, 5, dan 6 adalah simpul a, b, c, d, e, dan f. Setelah masing – msing bobot dimasukkan, maka terdapat hasil jalur terpendak dari simpul awal ke simpul tujuan, dengan jarak bobot yang terkecil, yaitu 10 untuk jarak a ke c, 25 untuk jarak a ke d, 45 untuk jarak a ke b, dan 45 untuk jarak a ke e. 4. Pembahasan dan Implementasi 4.1. Proses Jalannya Aplikasi Pada aplikasi ini, penulis menggunakan array untuk menyimpan simpul – simpul yang ada. Sedangkan untuk menyimpan simpul – simpul yang berdekatan digunakan matriks 2 x 2, dimana dalam matriks ini akan disimpan bobot yang menghubungkan
Gambar Uji Coba Tampilan Splash Screen
6
Ini adalah tampilan splashscreen dimana tampilan ini akan muncul beberapa menit sebelum tampilan jalur terpendek muncul. Tampilan ini berisi biografi tentang pembuat algoritma dijkstra. Setelah itu muncul tampilan jalur terpendek seperti dibawah ini : Gambar Uji Coba Tombol Process Seperti terlihat bahwa terdapat beberapa simpul yang dihubungkan dengan ruas yang memiliki bobot, yang bootnya dapat diatur besarnya. Kemudian adanya warna simpul awal yang berbeda dengan simpul tujuannya. Untuk mengulangi proses, dapat dilakukan dengan menekan tombol ‘Review’, maka graf akan kembali pada posisi awal dimana graf belum diproses. Tekan tombol ‘Step’ untuk melakukan proses secara langkah demi langkah agar lebih dapat dipahami. Proses ini akan berjalan dengan keterangan yang berada pada teks area untuk lebih memperjelas jalannya proses. Terdapat pula contoh yang disediakan oleh sistem seperti berikut:
Gambar Uji Coba Frame Jalur Terpendek Terdiri dari 1 buah kanvas, teks area, dan 8 buah button yang setiap tools memiliki fungsinya masing – masing. Maka hasilnya akan terlihat seperti dibawah ini :
Gambar Uji Coba Pembuatan Graf Setelah graf terbentuk, maka graf dapat disimpan dengan menekan tombol ‘Save’, kemudian graf dapat dipanggil kembali dengan menekan tombol ‘Load’. Setelah graf dipanggil kembali, maka dapat dijalankan prosesnya seperti berikut :
Gambar Uji Coba Tombol Example Untuk lebih jelasnya dalam menjalankan aplikasi ini, pembuat aplikasi menyediakan langkah – langkah penggunaannya, dengan
7
menekan tombol ‘Help’, tampilannya akan terlihat pada gambar berikut :
Edition) pada suatu graf dapat dilakukan dengan baik. b. Penggunaan algoritma dijkstra sebagai media pembelajaran dapat diproses dengan baik. c. Kompleksitas waktu (running time) yang dibutuhkan pada algoritma dijkstra lebih baik dibandingkan dengan algoritma Bellman-Ford. 4.2. Saran Penulis menyadari masih terdapat kekurangan dari aplikasi ini. Dengan demikian penulis berharap agar aplikasi ini dapat dikembangkan lagi kearah yang lebih baik dengan penyempurnaan dikemudian hari, misalnya saja dengan menggunakan bahasa pemrograman selain J2SE ataupun penggunaan algoritma yang berbeda untuk pencarian jalur terpendek ini.
Gambar Uji Coba Tombol Help Kemudian untuk menampilkan pembuat aplikasi, dapat menekan tombol ‘About’, tampilannya akan terlihat seperti dibawah ini:
5. Daftar Pustaka [1] Suryadi H.S., Pengantar Teori & Algoritma Graph, cetakan ketiga, Gunadarma, Jakarta, 1995. Gambar Uji Coba Tombol About Me
[2] Dwi Prasetyo, Didik. 2007. 150 Rahasia Pemrograman. Jakarta: Elex Media Komputindo.
Tampilan ini dibuat seperti ini agar user tidak perlu menampilkan banyak frame pada proses yang sama.
[3] Kadir, Abdul. 2007. Dasar Pemrograman JAVA 2. Yogyakarta: Andi.
Penutup 4.1. Kesimpulan Dari hasil pembahasan dan analisa yang telah dilakukan, penulis dapat menyimpulkan bahwa : a. Penggunaan algoritma dijkstra untuk mencari jalur terpendek menggunakan J2SE (Java 2 Standard
[4] URL:http://id.wikipedia.org/ wiki/Algoritma_Dijkstra, 22 Juni 2010. [5] URL:http://jenigroup.blogspot. com/2009/01/kekurangan-dankelebihan-java.html, 8 Mei 2010.
8
