My first Magazine pemrograman-kompetitif-dasar | Page 133

11.1 Shortest Path
2
2
5
6
1
3
3
1
5
2
dist
visited
pred
4
1
0
true
−1
2
2
true
1
3
5
true
4
4
3
true
1
5
6
f alse
3
Gambar 11.6: Tahap 5: Node yang belum dikunjungi dan memiliki nilai dist terkecil adalah 3.
Ubah nilai visited dan relax seluruh tetangganya. Hanya node 5 yang mengalami
perubahan dist.
2
2
1
5
6
3
3
1
5
2
1
0
true
−1
dist
visited
pred
4
2
2
true
1
3
5
true
4
4
3
true
1
5
6
true
3
Gambar 11.7: Tahap 6: Satu-satunya node yang belum dikunjungi adalah 5. Ubah nilai visited
dan relax seluruh tetangganya. Algoritma selesai.
Gambar 11.7 menunjukkan shortest path mulai dari node 1 ke seluruh node lainnya. Anda
dapat melihat kebenaran hasil algoritma Dijkstra dengan membandingkannya dengan pencarian
shortest path secara manual.
Sifat algoritma Dijkstra yang pada setiap tahapnya selalu memilih node berjarak tempuh
terkecil merupakan suatu bentuk greedy . Diasumsikan bahwa pengutamaan perjalanan yang jarak
tempuhnya terkecil saat itu akan menghasilkan shortest path yang benar. Hal ini akan selalu
benar untuk graf yang tidak memiliki bobot negatif. Untuk kasus graf yang memiliki bobot negatif,
asumsi ini tidak lagi memberikan shortest path yang optimal. Sebab mungkin saja terdapat suatu
jalur yang jarak tempuhnya sangat besar, tetapi pada akhirnya akan melewati edge dengan bobot
negatif yang besar pula. Perhatikan Gambar 11.8 untuk lebih jelasnya.
8
2
-7
4
1
1
3
6
Gambar 11.8: Contoh graf yang mengakibatkan algoritma Dijkstra gagal. Shortest path dari 1
ke 4 yang dihasilkan algoritma Dijkstra adalah melalui 1, 3, lalu 4 dengan jarak
total 7. Padahal, melalui 1, 2, lalu 4 memiliki jarak total 1.
Implementasi
Algoritma 62 menunjukkan implementasi untuk algoritma Dijkstra. Representasi graf yang
cocok untuk digunakan adalah adjacency list , sehingga pencacahan seluruh tetangga dari suatu
node efisien.
123