Algoritma Prim

Algoritma Prim adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai menghubungkan semua titik dengan biaya terendah.
Algoritma ini memiliki kemiripan struktur dengan Algoritma Floyd-Warshall yang sudah dijelaskan sebelumnya. Algoritma terkenal lainnya untuk menyelesaikan kasus yang sama adalah Algoritma Kruskal yang juga sudah dijelaskan sebelumnya.

Diasumsikan ada 5 titik yang harus dihubungkan semuanya, yaitu titik A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
Tentukan jalur yang harus diambil untuk menghubungkan semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut

Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

Const jumlahTitik As Integer = 5

Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi semua variabel yang diperlukan, yaitu variabel gambar, titik, garis, dan subset
Penjelasan tentang masing-masing class akan dijelaskan pada skrip dibawah ini

Console.WriteLine("Masukkan kata yang akan dicari usulannya: ")
Dim gmb As New Gambar(jumlahTitik)
Dim daftarTitik As Titik() = gmb.daftarTitik
Dim daftarGaris As New List(Of Garis)()
Dim grs As Garis

Dim hasil As Garis() = New Garis(jumlahTitik - 1) {}

* Agar dapat menjalankan skrip diatas, maka diperlukan 3 buah class
Class Titik digunakan untuk menampung data titik
Class Garis digunakan untuk menampung data titik awal, titik tujuan, dan biaya jalur tersebut
Class Gambar digunakan untuk menampung semua data titik dan semua data garis yang digunakan
Deklarasi masing-masing class adalah sebagai berikut:

Public Class Gambar
    Public daftarGaris As List(Of Garis) = Nothing
    Public daftarTitik As Titik() = Nothing

    Public Sub New(jumlahTitik As Integer)
        daftarTitik = New Titik(jumlahTitik - 1) {}
        For i As Integer = 0 To jumlahTitik - 1
            daftarTitik(i) = New Titik(Chr(i + 65))
        Next
    End Sub
End Class

Public Class Garis
    Private m_titikAwal As Titik
    Private m_titikTujuan As Titik
    Private m_biaya As Integer

    Public Property titikAwal() As Titik
        Get
            Return m_titikAwal
        End Get
        Set(value As Titik)
            m_titikAwal = value
        End Set
    End Property

    Public Property titikTujuan() As Titik
        Get
            Return m_titikTujuan
        End Get
        Set(value As Titik)
            m_titikTujuan = value
        End Set
    End Property

    Public Property biaya() As Integer
        Get
            Return m_biaya
        End Get
        Set(value As Integer)
            m_biaya = value
        End Set
    End Property

    Public Sub New(titikAwal As Titik, titikTujuan As Titik, biaya As Integer)
        m_titikAwal = titikAwal
        m_titikTujuan = titikTujuan
        m_biaya = biaya
    End Sub
End Class

Public Class Titik
    Private m_Label As String

    Public Property Label() As String
        Get
            Return m_Label
        End Get
        Set(value As String)
            m_Label = value
        End Set
    End Property

    Public Sub New(ByVal label As String)
        m_Label = label
    End Sub
End Class

2. Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia

grs = New Garis(daftarTitik(0), daftarTitik(1), 6)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(4), 7)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(2), 5)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(3), 4)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(4), 8)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(3), 7)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(4), 3)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(4), 9)
daftarGaris.Add(grs)

gmb.daftarGaris = daftarGaris.ToList().OrderBy(Function(p) p.biaya).ToList()

3. Inisialisasi array jalur sebanyak jumlah titik, dan array jarak antara 2 titik sebanyak jumlah titik

Dim jalur As Integer() = New Integer(jumlahTitik - 1) {}
Dim jarak As Integer()() = New Integer(jumlahTitik - 1)() {}
For i As Integer = 0 To jarak.Length - 1
	jarak(i) = New Integer(jumlahTitik - 1) {}
Next

4. Masukkan data jarak sesuai dengan data garis yang sudah dijelaskan pada nomor 2

Dim idxTitikAwal As Integer, idxTitikTujuan As Integer
For i As Integer = 0 To daftarGaris.Count - 1
	idxTitikAwal = daftarGaris(i).titikAwal.idx
	idxTitikTujuan = daftarGaris(i).titikTujuan.idx
	jarak(idxTitikAwal)(idxTitikTujuan) = daftarGaris(i).biaya
	jarak(idxTitikTujuan)(idxTitikAwal) = daftarGaris(i).biaya
Next

5. Lakukan perulangan sebanyak jumlah titik dikurangi 1 (poin 5a – 5d)

5a. simpan titik selanjutnya pada array jalur pada indeks yang sedang dihitung

jalur(i) = titikSelanjutnya
Dim idxTitikTerpilih As Integer = jalur(i)

5b. beri nilai 0 pada array jarak pada kolom titik terpilih

For j As Integer = 0 To jarak(0).Length - 1
	jarak(j)(idxTitikTerpilih) = 0
Next

5c. Lakukan perulangan pada nilai pada array jarak yang bernilai lebih dari 0
Apabila terdapat jarak yang lebih pendek dari biaya terendah sementara,
maka masukkan jarak terpendek tersebut sebagai biaya terendah, dan simpan kedua titik pembentuk garis tersebut

titikSelanjutnya = 0
For j As Integer = 0 To jarak.Length - 1
	For k As Integer = 0 To jarak(j).Length - 1
		idxTitikTerpilih = jalur(j)

		If jarak(idxTitikTerpilih)(k) <= biayaTerendah AndAlso jarak(idxTitikTerpilih)(k) > 0 Then
			biayaTerendah = jarak(idxTitikTerpilih)(k)
			titikSelanjutnya = k
			titikAwal = idxTitikTerpilih
		End If
	Next
Next

5d. Apabila biaya terendah bernilai 0 maka hentikan perhitungan.
Apabila biaya terendah bernilai selain 0, maka cari garis dari kedua titik yang ditemukan,
dan simpan garis tersebut sebagai salah satu jawaban jalur dengan biaya terendah

If biayaTerendah <> 0 Then
	jumlahBiaya += biayaTerendah
	For j As Integer = 0 To daftarGaris.Count - 1
		If daftarGaris(j).titikAwal.idx = titikAwal AndAlso daftarGaris(j).titikTujuan.idx = titikSelanjutnya Then
			hasil(iterasi) = daftarGaris(j)
			iterasi += 1
			Exit For
		End If
	Next
Else
	Exit For
End If

6. Catat hasil akhir untuk masing-masing jawaban garis yang ditemukan
Kemudian catat total biaya garis tersebut

For i As Integer = 0 To iterasi - 1
	Console.WriteLine("Jalur " & i + 1 & " adalah dari titik " & hasil(i).titikAwal.Label & " ke titik " & hasil(i).titikTujuan.Label & " dengan biaya " & hasil(i).biaya)
Next
Console.WriteLine("Total biaya = " & jumlahBiaya)

Hasil akhir adalah: (klik untuk perbesar gambar)

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:

Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.