Algorithma Graf & Pohon

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.

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/