My first Magazine pemrograman-kompetitif-dasar | Page 132

11 Algoritma Graf
2
2
5
6
1
3
3
1
5
dist
visited
pred
2
4
1
0
f alse
−1
2
∞
f alse
−1
3
∞
f alse
−1
4
∞
f alse
−1
5
∞
f alse
−1
Gambar 11.2: Tahap 1: Lakukan inisialisasi untuk seluruh data node . Perhatikan perbedaan nilai
inisialisasi untuk node permulaan, yaitu node 1.
2
2
5
6
1
3
3
1
5
2
dist
visited
pred
4
1
0
true
−1
2
2
f alse
1
3
6
f alse
1
4
3
f alse
1
5
∞
f alse
−
Gambar 11.3: Tahap 2: Node yang belum dikunjungi dan memiliki nilai dist terkecil adalah 1.
Tandainya dengan visited[1] = true, dan relax seluruh tetangganya.
2
2
5
6
1
3
3
1
5
2
dist
visited
pred
4
1
0
true
−1
2
2
true
1
3
6
f alse
1
4
3
f alse
1
5
7
f alse
2
Gambar 11.4: Tahap 3: Node yang belum dikunjungi dan memiliki nilai dist terkecil adalah 2.
Tandainya dengan visited[2] = true, dan relax seluruh tetangganya. Hanya node 5
yang mengalami perubahan dist. Kini diketahui pula bahwa edge h1, 2i merupakan
bagian dari shortest path ke 2.
2
2
1
5
6
3
3
2
4
1
5
dist
visited
pred
1
0
true
−1
2
2
true
1
3
5
f alse
4
4
3
true
1
5
7
f alse
2
Gambar 11.5: Tahap 4: Node yang belum dikunjungi dan memiliki nilai dist terkecil adalah 4.
Ubah nilai visited dan relax seluruh tetangganya. Node 3 mengalami perubahan
dist.
122