Djikstra
dinamai menurut penemunya,
seorang ilmuwan computer (Edsger Dijkstra), adalah sebuah algoritme
rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan
jarak terpendek (shortest path problem) untuk sebuah graf
berarah (directed graph) dengan bobot-bobot sisi (edge weights)
yang bernilai tak-negatif.
Langkah-Langkah
Membuat Djkstra:
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.
Penyelesaian:
Symbol Vertex:
V1= Panyipatan
V2=Sungairiam
V3= Karang Jawa
V4=Matah
V5=Tajau pecah
V6=Saranghalang
V7=Pom Angsau
1.
V1->V2->V3->V4->V6->V7
=23
2. V1->V2->V3->V5->V6->V7
=16
3. V1->V2->V3->V5->
V7 =18
4. V1->V3->V2->V5->V6->V7
=19
5. V1->V3->V2->V5
->V7=21
6. V1->V3->V5->V6->V7=17
7. V1->V3->V6->V7=20
8. V1->V3->V5->V7=19
9. V1->V3->V6->V5->V7=26
10. V1->V4->V3->V5->V6->V7=23
11. V1->V4->V6->V7=28
12. V1->V4->V6->V5->V7=22
Dengan demikian jarak terpendek dari V1/Panyipatan ke
V7/Pom Angsau adalah 16 dengan jalur V1->V2->V3->V5->V6->V7 /
Panyipatan->Sungairiam->Karang jawa->Tajau Pecah->Sarang
Halang->Pom Angsau
Kuskal
adalah sebuah algoritma dalam
teori graf yang mencari sebuah minimum spanning tree (MST) untuk sebuah graf
berbobot yang terhubung.
Langkah-Langkah
Membuat Kurskal:
1. Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi yang memiliki bobot terkecil.
1. Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi yang memiliki bobot terkecil.
2.
Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit pada
pohon, kemudian tambahkan sisi tersebut ke dalam pohon.
3.
Ulangi langkah kedua sebanyak n – 1 kali (n adalah jumlah simpul graf).
Dalam
pembuatan graf algoritma kruskal lintasannya tidak boleh membentuk circle.
Kelebihan Dan Kekurangan Algoritma
Kruskal
- Kelebihan
sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul. - Kekurangan
kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma ini menitik beratkan pada pencarian sisi yang diurutkan.
Sumber:
https://medium.com/@muhamadenrinal/minimum-spanning-tree-dengan-algoritma-prim-dan-kruskal-4aa9fd2b075
https://id.wikipedia.org/wiki/Algoritme_Dijkstra
http://student.blog.dinus.ac.id/mfadhilhabibie/2018/12/27/algoritma-kruskala-materi/
