in Uncategorized

Algoritma Dijkstra: Algoritma Populer yang Ditemukan Dalam 20 Menit

Reading Time: 5 minutes

Ulasan Singkat Algoritma Dijkstra

Algoritma ini merupakan salah satu algoritma yang popular digunakan untuk mencari lintasan atau rute terpendek pada suatu graf. Seorang ilmuan komputer asal Belanda bernama Edsger W. Dikstra mempublikasikannya temuannya pada tahun 1959 dengan judul “A note on two problems in connexion with graphs”.

Berdasarkan tulisan di freecodecamp, Dijkstra mengaku bahwasanya algoritma ini didesain hanya dalam waktu 20 menit. Pada suatu pagi di Amsterdam, ia belanja bersama tunangannya. Dia merasa kelelahan yang membuatnya memutuskan ke kafe dan minum segelas kopi panas. Waktu itu yang ada di kepalanya adakah jalan terdekat dari Rotterdam menuju Groningen?

Pada akhirnya ia menemukan algoritma, yang sangat membuatnya bangga. Tanpa kertas dan pensil, ia berhasil menyelesaikan kerumitan di kepalanya. Luar biasa memang.

Algoritma ini didasarkan pada beberapa konsepsi graph, seperti node, edge, atau juga bobot. Node merupakan suatu titik pada graph, yang mana dapat disebut pula sebagai simpul atau juga verteks. Adapun edge merupakan garis yang menghubungkan antar node, yang mana dapat berarah atau juga tidak. Adapun bobot ini mengacu pada bobot antar relasi dari setiap node.

Adapun berikut disampaikan beberapa hal dasar mengenai algoritma ini

  • Menggunakan prinsip greedy yang mana pada setiap langkah dari algoritma ini akan dipilih bobot minimum dan memasukkannya sebagai himpunan solusi
  • Digunakan untuk mencari jarak terpendek dari suatu node dengan node-node lain di dalam graph
  • Algoritma dijkstra dapat bekerja dengan baik untuk edge yang memiliki bobot positif.
  • Algoritma akan menemukan rute terpendek dari suatu node (sumber) dengan node lain yang mana dapat ditandai sebagai visited
  • Proses dari algoritma ini akan berhenti apabila semua node telah berhasil dikunjungi
Algoritma Dijkstra

Lebih lanjut proses atau algoritma dapat dituliskan Dijkstra adalah sebagai berikut

  1. Inisialisasi node yang menjadi node sumber (pertama)
  2. Hubungkan dengan node yang belum dikunjungi, yang mana node tersebut apabila dihubungkan memiliki rute terpendek
  3. Ulangi proses 2 sampai semua node dikunjungi atau dilewati

Contoh Kasus Penggunaan Algoritma Dijkstra

Misal diberikan graph sebagaimana pada gambar di atas. Terdapat 7 node, yaitu A, B, C, D, E, F, yang mana saling terhubung dan memiliki bobot sebagaimana pada gambar di atas.

Graph di atas pada dasarnya dapat dibentuk ke dalam suatu matrik adjacency, yaitu matrik yang merepresentasikan hubungan antar node sebagaimana pada gambar di atas. Dalam hal ini dapat diperoleh matrik adjacency sebagai berikut

Pada matriks di atas dituliskan null yang mana merupakan kejadian apabila suatu node tidak berhubungan dengan suatu node lainnya. Adapun 0 merepresentasikan suatu bobot apabila suatu node berhubungan dengan dirinya sendiri.

Dari sini kita dapat memulai langkah pencarian rute terpendek dengan menggunakan algoritma dijkstra. Langkah pertama adalah dengan menginisialisasi node awal yang menjadi menjadi sumber node. Dalam hal ini misalnya node sumber adalah A, sehingga jelas bahwa node A sudah dikunjungi. Dengan kata lain node yang belum dikunjungi adalah B, C, D, E, dan F.

Selanjutnya dari node sejumlah node yang belum dikunjungi diperhatikan node-node yang berhubungan dengan node yang sudah dikunjungi, yaitu A. Diperoleh bahwa ada node B dan C yang berpotensi dikunjungi berikutnya. Nah, di sinilah dipakai prinsip greedy dimana dipilih jarak atau edge yang terpendek. Dalam hal diperoleh C sebagai node terpendek, dengan bobot A→ C = 4 < 6 = A → B. Karenanya C menjadi dikunjungi dan diperoleh jarak terpendek A → C adalah 4. Adapun node-node yang belum dikunjungi tinggal B, D, E, dan F.

Proses selanjutnya kiranya sama dengan proses sebelumnya yaitu dengan memerhatikan node-node yang belum dikunjungi dan berhubungan dengan node node yang sudah dikunjungi. Dalam hal ini node yang sudah dikunjungi ada A dan C. Sementara itu node yang belum dikunjungi adalah B, D, E, dan F.

Didapati bahwa node yang belum dikunjungi yang berhubungan dengan A atau C adalah B dan D. Ingat bahwa dalam hal ini apabila menyebutkan daerah yang sudah dikunjungi maka node tersebut sudah mewakili jarak terpendek menuju node tersebut dari sumber node. Sebagai contoh A maka akan bernilai 0, lalu apabila C akan bernilai 4 yang mana berarti sama dengan bobot A →C. Selanjutnya karena bahwa A→B = 6 < A→ C → D = 7, maka node B akan dikunjungi dan diperoleh jarak terpendek A ke B adalah 6. Node yang belum dikunjungi tinggal D, E dan F.

Dengan proses yang sama akan diperoleh bahwa A → C → D = 7 < 11 = A → B → D, sehingga D dikunjungi dan jarak terpendek A→ D = 7. Adapun node-node yang belum dikunjungi tinggal E dan F.

Selanjutnya karena jarak terpendek menuju D adalah A → C → D dapat diperhatikan bahwa A→C→D→ E = 14 > 9 = A→ C → D → F. Dengan kata lain node yang berikutnya dikunjungi adalah F dan memiliki rute A→ C → D → F serta berbobot total 9. Adapun node yang belum dikunjungi tinggal E.

Pada tahap ini terdapat dua jalan menuju E, yaitu dari D atau juga dari F. Karena A→ C → D → E = 14 > 12 = A→ C → D → F → E maka dapat disimpulkan jarak terpendek dari A menuju E adalah 12 dengan rute A→ C → D → F → E.

Karena E telah dikunjungi maka seluruh node telah berhasil dikunjungi atau dilewati, sehingga proses jalannya algoritma ini selesai. Secara umum proses jalannya algoritma ini dapat tergambar sebagaimana pada tabel berikut

IterasiRuteJarak
1A0
2A→ C4
3A → B6
4A → C → D7
5A → C → D → F9
6A → C → D → F → E12
  •  
  •  
  •  
  •  
  •