Ulasan singkat tentang Algoritma Djidstra

• Pengertian tentang algoritma Djigstra

Saat ini sudah banyak algoritma yang bisa digunakan untuk menemukan pencarian rute terpendek, dan tidak bisa di pungkiri Djikstra masih menjadi salah satu yang populer dari sekian banyak algoritma tersebut. Pada postingan kali ini kita akan membahas mendetail mulai dari apa itu algoritma djikstra dan dan bagaimana cara kerja algoritma djikstra.

• Edsger Dijkstra

Algortima ini ditemukan oleh Edsger W. Dikstra dan di publikasi pada tahun 1959 pada sebuah jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs“[1]. Algoritma ini sering digambarkan sebagai algoritma greedy (tamak). Sebagai contoh, ada pada buku Algorithmics (Brassard and Bratley[1988, pp. 87-92])

Djikstra merupakan salah satu varian bentuk algoritma popular dalam pemecahan persoalan terkait masalah optimasi pencarian  lintasan terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo Code dan Flowchart Algoritma Djikstra:

Djikstra Flowchart

Implementasi Djikstra Algoritma ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titk lainnya. Misalnya titik mengambarkan gedung dan garis menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

• Cara Kerja

  

Cara kerja  Algoritma dijkstra memakai strategi greedy, dimana pada setiap langkah di pilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan  simpul yang sudah terpilih dengan simpul lain yang belum terpilih.             Algoritma Dijkstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir dari algoritma ini adalah jarak terpendek dari tempat asal ke tempat ujuan beserta  rutenya. Untuk bisa menerapkan algoritma ini dibutuhkan beberapa data yang harus disiapkan, yaitu : Beberapa Titik/simpul/daerah, titik/simpul/daerah yang bisa dijangkau secara langsung, dan juga jarak antara mereka. Titik/simpul/daerah awal. Titik/simpul/daerah tujuan. Jika dicontohkan dengan gambar grafik akan seperti ini : Titik A adalah titik awal dan titik F adalah titik tujuan. Kemudian kita akan mencari rute manakah yang harus dilewati dan memilik total jarak yang paling dekat. Untuk bisa mendapatkan rute itu, maka grafik diatas ditambahkan beberapa kotak untuk mengisi beberapa label. Seperti ini : Penjelasannya adalah :    Setelah itu ada beberapa langkah yang harus dilakukan, yaitu : Mengisi kotak label pada titik awal dengan label urutan 1 dan label jarak 0. Menetapkan label jarak sementara untuk semua titik yang dapat dihubungi langsung dari awal. Pilih titik dengan label jarak sementara terkecil dan menuliskan nilainya di label jarak, serta tambahkan label urutan-nya. Masukan label jarak sementara pada setiap titik yang belum memiliki label urutandan label jarak dan dapat dihubungi langsung dari titik yang baru saja ditulis label jarak dan label urutan-nya. nilainya diisi dengan total dari label jarak dari titik sebelumnya dan jarak dari titik tersebut. Jika label jarak sementara di titik tersebut sudah memiliki nilai, maka harus diganti hanya jika nilai yang baru lebih kecil. Pilih titik dengan label jarak sementara terkecil dan menggunakan label jarak sementara-nya sebagai label jarak dari titik tersebut, serta tambahkan label urutan-nya. Ulangi langkah 4 dan 5 hingga titik tujuan memiliki label jarak dan label urutan. Maka pada langkah pertama adalah Mengisi kotak label pada titik awal dengan label urutan 1 dan label jarak 0. Kemudian mengisi label jarak sementara titik yang dapat dihubungi langsung dari titik Ayakni titik B, C, dan E. Maka yang terpilih adalah titik B karena memiliki label jarak sementara terkecil, dan mengisi nilai label jarak-nya sama dengan label jarak sementara serta memberikan label urutan-nya.     Selanjutnya mengisi label jarak sementara titik yang belum memiliki label jarak dan dapat dihubungi langsung dari titik B yakni hanya titik C. Label jarak sementara titik C diisi dengan total jarak dari titik A sampai ke titik C yang melalui titik B, yakni 4 + 2 = 6. Namun sebelumnya nilai label jarak sementara-nya titik C sudah ada dan lebih kecil (5), jadi label jarak sementara-nya tidak diganti dan tetap bernilai 5. Langkah selanjutnya adalah memilih label jarak sementara terkecil. Karena titik E dan titik Cmemiliki label jarak sementara yang sama yakni 5, maka bisa memilih salah satu dari kedua titik tersebut. Misalkan titik C yang dipilih, maka berikan label jarak dan label urutan-nya. Kemudian titik yang dapat dihubungi secara langsung dari titik C dan belum memilik label jarak adalah titik E dan D. Titik E => 5 + 1 = 6, lebih besar jika dibandingkan dengan nilailabel jarak sementara yang dimiliki oleh titik E sebelumnya (5), maka nilai 6 diabaikan dan tetap diisi 5. Titik D => 5 + 2 = 7, maka langsung saja label jarak sementara titik D diisi dengan 7.   Selanjutnya titik E terpilih karena memiliki label jarak sementara terkecil. Berikan label jarak dan label urutan-nya. Dan titik F dan G adalah titik yang dapat dihubungi secara langsung dari titik E dan belum memilik label jarak. Titik F => 5 + 3 = 8 dan langsung diisikan kedalam label jarak sementara-nya. sedangkan titik D => 5 + 1 = 6 dan lebih kecil dari pada nilai sebelumnya yaitu 7, maka nilai label jarak sementara-nya diganti dengan 6. Maka titik D terpilih karena memiliki label jarak sementara terkecil. Berikan label jarak danlabel urutan-nya. Titik F adalah titik terakhir yang dapat dihubungi secara langsung dari titik D dan belum memilik label jarak serta merupakan titik tujuan. Titik F => 6 + 1 = 7 dan lebih kecil dari pada nilai sebelumnya yaitu 8, maka nilai label jarak sementara-nya diganti dengan 7. Karena titik F adalah stu-satunya titik terakhir yang belum mempunyai label jarak dan label urutan. maka lansung saja berikan nilai label jarak dan label urutan-nya. Dengan begitu titiktujuan sudah memiliki label jarak dan label jarak sementara. Cara mengetahui rute yang harus dilewati Untuk mengetahui rute manakah yang harus dilewati adalah dengan menelusuri kembali dari titik tujuan ke titik awal. tuliskan label jarak di samping setiap titik. Titik mana sajakah yang dapat dihungi langsung dari titik F ?, Yakni titik E dan D. maka, untuk menentukan titik manakah yang seharusnya dilewati adalah dengan cara mengurangkan label jarak titik F dengan jaraknya ke titik tujuan serta label jarak titik tersebut. jika hasilnya kurang dari 0 maka titik tersebut tidak layak untuk dilewati, dan jika hasilnya lebih dari 0 serta lebih mendekati 0 maka titik tersebut yang seharusnya dilewati. Langkah pertama : Langkah kedua : Langkah ketiga : Dengan begitu diketahui rute yang harus dilewati dan memiliki jarak terpendek dari titik Amenuju titik F adalah A -> E -> D -> F C.     Penerapan Algoritma Dijkstra   (Penerapan  Algoritma Dijkstra pada Jaringan Komputer) Mencari lintasan terpendek  dari router asal ke router tujuan dapat diartikan sebagai menentukan lintasan terpendek dari simpul asal ke simpul tujuan di dalam graf yang merepresentasikan jaringan komputer tersebut. Algoritma Dijkstra adalah algoritma yang banyak digunakan untuk mencari lintasan terpendek. Note : Bahkan menurut Andrew Goldberg, peneliti utama di Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan,” – Goldberg. “Industri selalu datang dengan aplikasi baru sepanjang waktu, membuat parameter yang berbeda untuk tiap masalah. Teknologi dengan lebih banyak kecepatan dan kapasitas memungkinkan kita untuk memecahkan masalah yang lebih besar, sehingga dalam lingkup masalah jalan terpendek maka akan selalu ada optimasi.