Page 21 - CalonFlipSearching

C. Djikstra
Algoritma Dijkstra merupakan salah satu bentuk algoritma yang

populer untuk memecahkan persoalan yang terkait dengan

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

note 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. Berikut cara
kerja algoritma Dijkstra:

1. Pengambilan edge dengan bobot terkecil dari node utama

2. Node tujuan dari edge tersebut ditandai dengan visited,

bobot total, dan path dari node sebelumnya

3. Semua edge yang menuju node tujuan dihapus (tidak
dilewati)

4. Semua edge yang keluar dari node tujuan dimasukkan ke

priority queue dengan tambahan bobot dari node tersebut

Kelebihan dijkstra adalah:
1. Dijkstra merupakan algoritma yang digunakan untuk

memetakan jalur aternatif, apabila jalur utama mengalami

hambatan

2. Mampu menyelesaikan permasalahan rute terpendek dan
aliran maksimum, elemen (bobot) dari rute tersebut berupa

harak tempuh, biaya, atau yang lainnya

Kekurangan dijkstra adalah:

13