My first Magazine pemrograman-kompetitif-dasar | Page 130

11
Algoritma Graf
Setelah Anda memahami cara merepresentasikan dan menyelesaikan persoalan graf seder-
hana, kini waktunya untuk mempelajari algoritma graf yang lebih rumit. Algoritma yang akan
dipelajari pada bab ini adalah penyelesaian untuk permasalahan yang klasik pada graf, yaitu
pencarian shortest path dan Minimum Spanning Tree (MST).
Untuk memulai pembahasan tentang algoritma graf, asumsikan:
•
•
•
•
•
V menyatakan banyaknya node .
E menyatakan banyaknya edge .
w[a][b] menyatakan bobot edge yang menghubungkan node a dengan node b.
Node pada graf dinomori dari 1 sampai dengan V .
ad j(x) menyatakan himpunan node yang merupakan tetangga dari node x.
11.1
Shortest Path
Salah satu persoalan umum yang dihadapi pada permasalahan graf adalah pencarian shortest
path (jalur terpendek). Definisi masalah yang diberikan adalah: diberikan graf, cari serangkaian
edge yang perlu dilalui mulai dari suatu node menuju suatu node lainnya, sedemikian sehingga
jumlah bobot dari edge yang dilalui sekecil mungkin. Pada kasus graf tidak berbobot, kita dapat
mengasumsikan bobot setiap edge adalah 1.
Definisi bobot dan jalur terpendek bergantung pada masalah yang dihadapi. Misalnya bobot
edge pada suatu graf yang merepresentasikan kota dan jalan menyatakan waktu tempuh, berarti
shortest path menyatakan total waktu tempuh paling sedikit yang diperlukan untuk berpindah
dari suatu kota ke kota lainnya.
Terdapat beberapa algoritma yang menyelesaikan masalah shortest path . Apabila kita
diberikan graf yang tidak berbobot, pencarian shortest path dapat menggunakan penelusuran
graf secara BFS. Untuk graf berbobot, diperlukan algoritma yang lebih kompleks. Pada bab
ini, kita akan mempelajari algoritma Dijkstra, Bellman—Ford, dan Floyd—Warshall. Nama ketiga
algoritma tersebut berasal dari nama pencipta-penciptanya.
11.1.1
Dijkstra
Konsep
Algoritma Dijkstra menggunakan konsep greedy untuk menemukan shortest path dari suatu
node , misalnya s, ke semua node lainnya. Untuk setiap tahapan, diperlukan pencatatan informasi
berikut untuk seluruh node :
• dist[x]: jarak terpendek yang sejauh ini ditemukan untuk mencapai node x dari node s.
120