My first Magazine pemrograman-kompetitif-dasar | Page 131

11.1 Shortest Path
• visited[x]: bernilai true apabila suatu node x telah dikunjungi.
Sebagai tambahan, kita juga dapat mencatat node mana yang dikunjungi sebelum mencapai
suatu node x pada shortest path . Kita nyatakan node tersebut sebagai pred[x]. Informasi ini
diperlukan apabila Anda membutuhkan edge -edge mana yang perlu digunakan pada shortest
path .
II Sekilas Info JJ
Apabila soal yang dihadapi tidak membutuhkan informasi edge -edge yang perlu diguna-
kan pada shortest path , Anda dapat menghemat waktu dan pengetikan kode dengan
mengabaikan pred[x].
Pada awalnya, seluruh node x memiliki nilai dist[x] = ∞, dan visited[x] = f alse. Khusus untuk
node s, kita mengetahui bahwa jarak terpendek untuk mencapai s dari s sendiri adalah 0. Oleh
sebab itu, dist[s] = 0. Seluruh nilai pred[x] bisa kita isi −1, sebab tidak diketahui node mana yang
dikunjungi sebelum x.
Setelah inisialisasi selesai dilakukan, jalankan langkah-langkah berikut:
1. Pilih sebuah node yang belum dikunjungi dan memiliki dist terkecil. Sebut saja node ini
sebagai u.
2. Apabila tidak ada lagi node yang belum dikunjungi, atau dist[u] bernilai ∞, artinya tidak ada
lagi node yang dapat dikunjungi. Algoritma Dijkstra berakhir.
3. Karena u dikunjungi, maka set visited[u] = true. Kini dipastikan shortest path dari s menuju
u adalah dist[u]. Diketahui pula edge hpred[u], ui merupakan edge yang perlu digunakan
pada shortest path ke u.
4. Untuk setiap node v yang merupakan tetangga dari u, lakukan sebuah proses yang disebut
"relax ". Proses relax untuk node u dan v adalah proses untuk memperbaharui jarak
terpendek mencapai v, apabila ternyata mencapai v melalui u membutuhkan jarak yang lebih
kecil. Dengan kata lain, dilakukan:
dist[v] = min(dist[v], dist[u] + w[u][v])
Setiap kali dist[v] mengalami perubahan, ubah nilai pred[v] menjadi u. Sebab sejauh ini
diketahui bahwa untuk mencapai v pada shortest path , node sebelumnya adalah u.
5. Kembali ke langkah 1.
Mari kita simulasikan Dijkstra pada graf berbobot dan tidak berarah yang ditunjukkan pada
Gambar 11.1. Misalnya node permulaan adalah 1, sehingga kita hendak mencari shortest path
dari 1 ke semua node lainnya. Gambar 11.2 sampai Gambar 11.7 menunjukkan simulasi Dijkstra
pada graf tersebut.
2
2
1
5
6
3
3
1
5
2
4
Gambar 11.1: Graf berbobot dan tidak berarah.
121