Mari kita selesaikan soal tersebut langkah demi langkah sesuai ketentuan.

a. Minimum Spanning Tree (MST) menggunakan Kruskal Algorithm:

Kruskal Algorithm bekerja dengan memilih edge yang memiliki bobot terkecil terlebih dahulu, kemudian menambahkannya ke dalam Minimum Spanning Tree (MST) dengan syarat tidak ada siklus yang terbentuk.

Langkah-langkah Kruskal:

1. Urutkan semua edge dari bobot terkecil ke terbesar.
2. Tambahkan edge satu per satu ke MST, pastikan tidak membentuk siklus.
3. Ulangi sampai semua node terhubung.

Urutan edge dari bobot terkecil:

• $E \rightarrow F$ : 1
• $A \rightarrow G$ : 2
• $C \rightarrow D$ : 2
• $D \rightarrow E$ : 3
• $H \rightarrow F$ : 4
• $E \rightarrow J$ : 6
• $G \rightarrow H$ : 5
• $B \rightarrow D$ : 4
• $A \rightarrow B$ : 11
• $G \rightarrow C$ : 12
• $J \rightarrow I$ : 3

Proses membangun MST:

1. Mulai dengan edge $E \rightarrow F$ (1) (tambahkan ke MST)
2. Tambahkan edge $A \rightarrow G$ (2) (tidak ada siklus)
3. Tambahkan edge $C \rightarrow D$ (2) (tidak ada siklus)
4. Tambahkan edge $D \rightarrow E$ (3) (tidak ada siklus)
5. Tambahkan edge $H \rightarrow F$ (4) (tidak ada siklus)
6. Tambahkan edge $E \rightarrow J$ (6) (tidak ada siklus)

Terbentuknya MST pada tahap ini sudah menghubungkan semua simpul (nodes), dan kita berhenti.

Minimum Spanning Tree dengan Kruskal (hasil gambar akan dibuat).

b. Minimum Spanning Tree menggunakan Prim's Algorithm:

Prim's Algorithm bekerja dengan memilih node awal dan kemudian menambah node terdekat dengan bobot terkecil yang belum dikunjungi.

Langkah-langkah Prim:

1. Mulai dari node $A$.
2. Pilih edge dengan bobot terkecil dari node $A$, tambahkan node yang terhubung.
3. Pilih edge dengan bobot terkecil dari node-node yang sudah ada di MST.
4. Ulangi sampai semua node terhubung.

Langkah-langkah:

1. Mulai dari $A$. Pilih $A \rightarrow G$ (2).
2. Dari node yang terhubung (A, G), pilih edge terkecil, yaitu $G \rightarrow C$ (5).
3. Dari (A, G, C), pilih $C \rightarrow D$ (2).
4. Dari (A, G, C, D), pilih $D \rightarrow E$ (3).
5. Dari (A, G, C, D, E), pilih $E \rightarrow F$ (1).
6. Dari (A, G, C, D, E, F), pilih $F \rightarrow H$ (4).
7. Dari (A, G, C, D, E, F, H), pilih $E \rightarrow J$ (6).

MST selesai terbentuk setelah semua node terhubung.

c. Shortest Path dari $B \rightarrow I$

Untuk menyelesaikan ini, kita akan menggunakan algoritma Dijkstra untuk menemukan jalur terpendek.

Langkah-langkah:

1. Tentukan jarak terpendek dari $B$ ke semua node.
2. Jalur yang harus dilewati dari $B \rightarrow I$ dihitung melalui jalur yang menghasilkan bobot total terkecil.

Saya akan menghitung total jaraknya.

Jalur terpendek dari B ke I:

• Dari B ke D (3)
• Dari D ke E (3)
• Dari E ke J (6)
• Dari J ke I (3)

Total bobot: 3 + 3 + 6 + 3 = 15

Saya akan membuat gambar dari Minimum Spanning Tree (MST) hasil Kruskal dan Prim.

Mari kita lanjutkan jika Anda ingin melihat visualisasi MST yang dihasilkan.