DJIKSTRA dan KKURSKAL
Oleh:
RABIATUL
MARDIYAH 1801301057
CAHYO DWI
SAPUTRA 1801301009
NANDA SETIA WATI
1801301048
AHMAD TRIADMOJO
1801301010
Dosen Pengampu:
Winda Aprianti,
M.Si
DAFTAR ISI
BAB I
DJIKSTRA
1.1 Pengertian Djikstra
Algoritme
Dijkstra adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan
jarak terpendek (shortest path problem) untuk sebuah graf berarah
(directed graph).
Algoritma
ini dioublikasikan pada tahun 1959 jurnal Numerische Mathematik yang
berjudul “A Note on Two Problems in Connexion with Graphs” dan dianggap
sebagai algoritma greedy.
Permasalahan rute terpendek dari sebuah titik ke
akhir titik lain adalah sebuah masalah klasik optimasi yang banyak digunakan
untuk menguji sebuah algoritma yang diusulkan. Permasalahan rute terpendek
dianggap cukup baik untuk mewakili masalah optimisasi, karena permasalahannya
mudah dimengerti (hanya menjumlahkan seluruh edge yang dilalui) namun memiliki
banyak pilihan solusi.
Menurut Andrew
Goldberg peneliti Microsoft Research Silicon Valley, mengatakan ada
banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan
terpendek. “Jalan terpendek adalah masalah optimasi yang relevan untuk
berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan
pemetaan”.
Diskripsi
matematis untuk grafik dapat diwakili G = {V. E}, yang berarti sebuah
grafik (G) didefenisikan oleh satu set simpul (Vertex = V) dan
koleksi Edge (E). Algoritma Dijkstra bekerja dengan membuat jalur ke
satu simpul optimal pada setiap langkah. Jadi pada langkah ke n, setidaknya ada
n node yang sudah kita tahu jalur terpendek.
Langkah-langkah
algoritma Dijkstra dapat dilakukan dengan langkah-langkah berikut:
1.
Tentukan
titik mana yang akan menjadi node awal, lalu beri bobot jarak pada node pertama
ke node terdekat satu per satu, Dijkstra akan melakukan pengembangan pencarian
dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap.
2.
Beri
nilai bobot (jarak) untuk setiap titik ke titik lainnya. Set semua node yang
belum dilalui dan set node awal sebagai “Node keberangkatan”
3.
Dari
node keberangkatan, pertimbangkan node tetangga yang belum dilalui dan hitung
jaraknya dari titik keberangkatan. Jika jarak ini lebih kecil dari jarak
sebelumnya (yang telah terekam sebelumnya) hapus data lama, simpan ulang data
jarak dengan jarak yang baru
4.
Saat
kita selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node
yang telah dilalui sebagai “Node dilewati”. Node yang dilewati tidak akan
pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang
paling minimal bobotnya.
5.
Set
“Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai
“Node Keberangkatan” selanjutnya dan ulangi langkah e.
Gambar 1.1 Contoh Hasil
Membuat Djikstra
1.2 Penjelasan Program
A. Coding Djikstra
B.
Hasil Running Program
BAB II
KRUSKAL
2.1 Pengertian Kruskal
Algoritma
kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum
spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan
subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik , di
mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak
terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk
setiap komponen terhubung ) . Algoritma Kruskal juga tergolong algoritma Greedy
dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma
ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan yang ditulis oleh Joseph
Kruskal. Algoritma Kruskal adalah contoh dari algoritma rakus . Algoritma
ini pertama kali muncul dalam Prosiding American Mathematical Society , hal
1956.
Dasar
pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing
forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf
G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya
ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya
iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin
sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest.
Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai
hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah
pohon yang merentang minimum.
Graph : kumpulan dua himpunan yaitu
himpunan titik ( vertex / simpul / node ) dan kumpulan dari garis ( edge ).
Tree : graph tak berarah yang
terhubung dan tidak mengandung sirkuit. Sirkuit : simpul awal = simpul akhir.1
Secara Umum Algoritma Kruskal
ditulis :
1. T masih kosong .
2. pilih sisi (i,j) dengan bobot
minimum.
3. pilih sisi (i,j) dengan bobot
minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T.
4. Ulangi langkah 3 sebanyak (n-2)
kali.
5. Total langkah (n-1) kali.
2.1.1 Karakteristik Algoritma Kruskal
Sifat Algoritma Kruskal ini:
1. Ia bekerja tidak hanya dengan grafik
diarahkan.
2. Ia bekerja dengan bobot dan tidak
grafik tertimbang. Tapi, yang lebih menarik, apabila tepi yang berbobot.
3. Kruskal adalah jenis algoritma
serakah yang menghasilkan solusi optimal MST.
2.1.2 Kelebihan dan Kekurangan Algoritma Kruskal
Terdapat dua macam algoritma tipe
greedy yang dapat memenuhi pemecahan masalah pohon merentang ini. Yaitu
algoritma Prim dan algoritma kruskal, berikut adalah kelebihan dan kekurangan
algoritma Kruskal dibanding algoritma prim.
a) Kelebihan
Algoritma Kruskal
Kelebihan algoritma Kruskal
dibanding algoritma prim adalah sebagai berikut:
Sangat cocok diterapkan saat graf
memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena
orientasi kerja algoritma ini adalah berdasarkan pada urutan bobot sisi, tidak
berdasarkan simpul.
b)
Kekurangan Algoritma Kruskal
Beberapa hal yang menjadi kekurangan
algoritma kruskal dibanding algoritma prim :
Kurang cocok digunakan saat graf
lengkap atau yang mendekati lengkap, dimana setiap simpul terhubungkan dengan
semua simpul yang lain. Karena algoritma Kruskal menitik beratkan pada
pencarian sisi, dimana sisi-sisi tersebut harus diurutkan dan ini memakan waktu
yang tidak sedikit
Contoh
Penyelesaian dengan Algoritma Kruskal
Contoh
penyelesaian kasus minimun spanning tree dengan algoritma kruskal, diketahui
sebuah graf berbobot seperti gambar 2.10 dibawah ini
Tabel 2. 1 Daftar urut nilai Graf dari sisi terbesar sampai
terkecil
|
Bobot
|
Ruas
|
||
|
15
|
D,E
|
||
|
9
|
B,D
|
E,F
|
|
|
8
|
B,C
|
B,E
|
F,G
|
|
7
|
A,D
|
C,E
|
|
|
6
|
A,B
|
E,G
|
|
|
5
|
D,F
|
Penyelesaian :
- Mula-mula kita buat sekumpulan titik G hanya terdiri
dari simpulsimpul saja.
- Urutkan Ruas dari bobot kecil ke besar (DF, AB, EG, AD, CE, BC, BE, FG, BD, EF, DE), kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan mencegah terbentuknya sirkuit.
Spanning Tree adalah sebagai berikut
:
- Pilih ruas terkecil dari keseluruhan graf secara acak. Ruas DF adalah ruas terkecil dengan bobot 5 (gambar 2.11 (a))
- Setelah ruas 1 didapatkan, ulangi lagi pemilihan ruas terkecil secara acak dari keseluruhan graf. Ruas AB dan ruas EG adalah ruas terkecil dengan bobot 6. Pilih acak ruas AB (Gambar 2.11(b))
- Lanjutkan untuk ruas yang selanjutnya, Ruas EG adalah ruas terkecil dengan bobot 6 dan tidak membentuk sirkuit jika dihubungkan. Maka pilih ruas EG (Gambar 2.11(c))
- Pilih ruas selanjutnya dengan bobot yg terkecil saat ini, yaitu ruas AD dan ruas CE dengan bobot 7. Pilih acak ruas AD (Gambar 2.11(d))
- Lanjutkan untuk ruas CE adalah ruas terkecil dengan 7 dan tidak membentuk sirkuit jika dihubungkan. Maka pilih ruas CE (Gambar 2.11(e))
- Ruas selanjutnya dengan bobot yg terkecil saat ini yaitu ruas BC, BE dan FG dengan bobot 8. Pilih acak ruas BC dan hapus ruas BE (Gambar 2.11(f)) dan ruas FG karena akan membentuk sirkuit jika dihubungkan (Gambar 2.11(g))
- Untuk ruas-ruas selanjutnya, BD, EF,dan DE dihapus karena akan membentuk sirkut jika dihubungkan (Gambar 2.11(h), Gambar 2.11(i), Gambar 2.11(j))
- Gambar 2.11(k) adalah Minimum Spanning Tree yang dihasilkan.
2.3 Penjelasan Program
A. Algoritma Kruskal
B. Hasil Running Program
BAB
III
KASUS ALGORITMA KRUSKAL DAN DJIKSTRA
3.1 Map
3.2 Graf Kruskal
3.3 Graf Djikstra
3.4 Matriks Kruskal
|
|
1
|
2
|
3
|
4
|
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
|
|
1
|
0
|
2100
|
0
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
3200
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
2100
|
0
|
2000
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
0
|
2000
|
0
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
|
1500
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
0
|
0
|
1500
|
|
|
|
400
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
5
|
0
|
0
|
0
|
|
|
|
0
|
3500
|
0
|
0
|
0
|
0
|
0
|
700
|
0
|
|
|
|
|
400
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
6
|
0
|
0
|
0
|
|
|
|
3500
|
0
|
400
|
0
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
7
|
0
|
0
|
0
|
|
|
|
0
|
400
|
0
|
200
|
0
|
0
|
0
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
8
|
0
|
0
|
0
|
|
|
|
0
|
0
|
200
|
0
|
2300
|
0
|
0
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
9
|
0
|
0
|
0
|
|
|
|
0
|
0
|
2300
|
0
|
0
|
4000
|
0
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
10
|
0
|
0
|
0
|
|
|
|
0
|
0
|
0
|
0
|
4000
|
0
|
1700
|
0
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
11
|
0
|
0
|
0
|
|
|
|
0
|
0
|
0
|
0
|
0
|
1700
|
0
|
1600
|
0
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
12
|
0
|
0
|
0
|
|
|
|
0
|
0
|
0
|
0
|
0
|
0
|
1600
|
0
|
300
|
|
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
13
|
3200
|
0
|
0
|
0
|
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
300
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
3.5 Matriks Djikstra
|
|
0
|
|
1
|
|
2
|
|
3
|
|
4
|
|
5
|
|
6
|
|
7
|
|
8
|
|
9
|
|
10
|
|
11
|
|
12
|
|
|||||||||||||
|
0
|
|
0
|
|
|
2100
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
3200
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
|
2100
|
|
|
0
|
|
|
2000
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2
|
|
2000
|
|
|
0
|
|
|
0
|
|
|
1500
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3
|
|
0
|
|
|
0
|
|
|
1500
|
|
|
0
|
|
|
400
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4
|
|
0
|
|
|
0
|
|
|
0
|
|
|
400
|
|
|
0
|
|
|
3500
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
700
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
3500
|
|
|
0
|
|
|
400
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
400
|
|
|
0
|
|
|
200
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
7
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
200
|
|
|
0
|
|
|
2300
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
2300
|
|
|
0
|
|
|
4000
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
4000
|
|
|
0
|
|
|
1700
|
|
|
0
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
1700
|
|
|
0
|
|
|
1600
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
700
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
1600
|
|
|
0
|
|
|
300
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12
|
|
3200
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
0
|
|
|
300
|
|
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3.6 Hasil Running Kruskal
3.7 Hasil Running Djikstra
BAB IV
PENUTUP
3.1 Kesimpulan
Algoritma Dijkstra merupakan sebuah
algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk
sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif. Sedangkan
Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah
minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti
menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap
titik , di mana berat total dari semua tepi di atas pohon diminimalkan. Jadi
algoritma djikstra merupakan pencarian nilai pendek dengan meggunakan bobot
sisi yang bernilai positif sedangkan algoritma Kruskal dia mencari nilai
minimum dengan menemukan subset dari sebuah pohon yang mencakup setiap titik.
Tidak ada komentar:
Posting Komentar