Page 23 - Searching Dosen

masalah optimasi dan bersifat sederhana. Algoritma dijkstra
ditemukan oleh Edger Wybe Dijkstra. Dijkstra dikenal sebagai

algoritma yang mampu menyelesaikan masalah dengan rute

pencarian terpendek menggunakan prinsip greedy (penyelesaian

masalah dengan pencarian nilai maksimum) (Siswanto, 2013). Prinsip
greedy yaitu mencari jalur terpendek dari satu node (titik/vertex) ke

node lain yang searah (directed graph), dimulai dari node awal

sampai pada node tujuan. Pada dasarnya vertex disimpan pada

array, dan edge (bobot) dari suatu vertex yang disimpan pada map

dalam array. Ilustrasi cara kerja dijkstra dapat dilihat pada Gambar
5.

Gambar 5 Cara Kerja Dijkstra

Berikut langkah-langkah cara kerja strategi pencarian dijkstra

berdasarkan ilustrasi Gambar 5, dengan node awal 1 dan node

tujuan 5:

1. Melakukan pengambilan edge (garis yang berbobot positif)

dengan bobot terkecil dari node utama (node 1).
2. Amati node mana saja yang terhubung dengan node

pertama, kemudian jumlahkan node pertama dengan node

yang terhubung langsung (node 2, 3, 6) dan pilihlah hasil
penjumlahan bobot yang paling kecil (node 2)

3. Ulangi langkah 2 sesuai dengan tempat terakhir node

dikunjungi (node 2), dimana node tersebut terhubung

15