Algoritma Bellman-Ford 7

Algoritma Bellman-Ford adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan jarak terpendek.

Diasumsikan ada sebaran titik yang harus dilalui semuanya
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki bobot sendiri-sendiri
Tentukan Jalur yang harus diambil untuk mengelilingi semua titik dengan jarak terpendek
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Contoh data awal adalah sebagai berikut:

bobotA.Add(6)
bobotA.Add(7)
garisA.Add(titikB)
garisA.Add(titikE)

bobotB.Add(5)
bobotB.Add(-4)
bobotB.Add(8)
garisB.Add(titikC)
garisB.Add(titikD)
garisB.Add(titikE)

bobotC.Add(-2)
garisC.Add(titikB)

bobotD.Add(7)
garisD.Add(titikC)

bobotE.Add(-3)
bobotE.Add(9)
garisE.Add(titikC)
garisE.Add(titikD)

titikA.tetangga = garisA
titikA.bobot = bobotA

titikB.tetangga = garisB
titikB.bobot = bobotB

titikC.tetangga = garisC
titikC.bobot = bobotC

titikD.tetangga = garisD
titikD.bobot = bobotD

titikE.tetangga = garisE
titikE.bobot = bobotE

Dim daftarTitik As New List(Of Titik)()
daftarTitik.Add(titikA)
daftarTitik.Add(titikB)
daftarTitik.Add(titikC)
daftarTitik.Add(titikD)
daftarTitik.Add(titikE)

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

Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan proses pencarian jalur dengan metode Bellman-Ford
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1a – 1e)

If BellmanFord(titikTujuan, daftarTitik) Then
. . .

Memasuki perhitungan pada fungsi BellmanFord

1a. Lakukan inisialisasi variabel titik tujuan sebanyak jumlah titik
variabel ini digunakan untuk menyimpan titik tujuan pada masing-masing indeks titik
Beri nilai awal pada pasing-masing titik tujuan dengan angka -1

titikTujuan = New Integer(daftarTitik.Count - 1) {}
For i As Integer = 0 To titikTujuan.Length - 1
	titikTujuan(i) = -1
Next

1b. Beri nilai awal jarak pada titik awal dengan 0

daftarTitik(0).jarak = 0

1c. Lakukan perulangan pada semua titik awal secara terurut
Untuk masing-masing titik awal, lakukan perulangan pada semua titik tujuan yang ditemukan (poin 1c1 – 1c2)

For i As Integer = 0 To daftarTitik.Count - 2
	Dim titikAwalTerpilih As Titik = daftarTitik(i)

	For j As Integer = 0 To titikAwalTerpilih.tetangga.Count - 1
		Dim titikTujuanTerpilih As Titik = titikAwalTerpilih.tetangga(j)
		. . .

1c1. jika jarak dari titik tujuan lebih dari jarak titik awal ditambah bobotnya,
maka pilih titik awal ini sebagai titik tujuan

If titikTujuanTerpilih.jarak > titikAwalTerpilih.jarak + bobot Then
	titikTujuanTerpilih.jarak = titikAwalTerpilih.jarak + bobot
	titikTujuan(titikTujuanTerpilih.Id) = titikAwalTerpilih.Id
End If

1c2. lakukan perulangan terhadap semua titik tetangga dari titik tujuan (poin 1c2a)

For k As Integer = 0 To titikTujuanTerpilih.tetangga.Count - 1
	Dim titikTujuanTetanggaTerpilih As Titik = titikTujuanTerpilih.tetangga(k)
	. . .

1c2a. jika jarak dari titik tetangga lebih dari jarak titik tujuan ditambah bobotnya,
maka pilih titik tetangga ini sebagai titik tujuan

If titikTujuanTetanggaTerpilih.jarak > titikTujuanTerpilih.jarak + bobot Then
	titikTujuanTetanggaTerpilih.jarak = titikTujuanTerpilih.jarak + bobot
	titikTujuan(titikTujuanTetanggaTerpilih.Id) = titikTujuanTerpilih.Id
End If

1d. Lakukan perulangan pada semua titik awal dan titik tujuan
jika jarak dari titik tujuan lebih dari jarak titik awal ditambah bobotnya,
maka hentikan perhitungan dan kembalikan nilai fungsi ini dengan nilai false

For i As Integer = 0 To daftarTitik.Count - 1
	Dim titikAwalTerpilih As Titik = daftarTitik(i)

	For j As Integer = 0 To titikAwalTerpilih.tetangga.Count - 1
		Dim titikTujuanTerpilih As Titik = titikAwalTerpilih.tetangga(j)
		Dim bobot As Integer = titikAwalTerpilih.bobot(j)

		If titikTujuanTerpilih.jarak > titikAwalTerpilih.jarak + bobot Then
			Return False
		End If
	Next
Next

1e. Jika kondisi nomor 4 tidak terpenuhi, maka kembalikan nilai fungsi ini dengan nilai true

Return True

2. Catat hasil akhir untuk masing-masing jawaban jarak yang ditemukan
Kemudian hitung total jarak dengan menjumlahkan semua jarak yang ditemukan

For i As Integer = 0 To titikTujuan.Count - 1
	If titikTujuan(i) <> -1 Then
		For iCount As Integer = 0 To daftarTitik(titikTujuan(i)).tetangga.Count - 1
			If i = daftarTitik(titikTujuan(i)).tetangga(iCount).Id Then
				jarak = daftarTitik(titikTujuan(i)).tetangga(iCount).jarak
				totalJarak += jarak
				Exit For
			End If
		Next

		Console.WriteLine("Jalur " & i & " adalah dari titik " & daftarTitik(titikTujuan(i)).nama & " ke titik " & daftarTitik(i).nama & " dengan jarak " & jarak)
	End If
Next

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class Titik untuk menampung semua data titik beserta jalurnya. Deklarasi Class Titik adalah sebagai berikut:

Class Titik
    Private m_jarak As Integer
    Private m_id As Integer
    Private m_nama As String
    Private m_bobot As List(Of Integer)
    Private m_tetangga As List(Of Titik)

    Public Sub New(jarak As Integer, id As Integer, nama As String)
        Me.m_jarak = jarak
        Me.m_id = id
        Me.m_nama = nama
        m_bobot = New List(Of Integer)()
        m_tetangga = New List(Of Titik)()
    End Sub

    Public Property jarak() As Integer
        Get
            Return m_jarak
        End Get
        Set(value As Integer)
            m_jarak = value
        End Set
    End Property

    Public Property Id() As Integer
        Get
            Return m_id
        End Get
        Set(value As Integer)
            m_id = value
        End Set
    End Property

    Public Property nama() As String
        Get
            Return m_nama
        End Get
        Set(value As String)
            m_nama = value
        End Set
    End Property

    Public Property tetangga() As List(Of Titik)
        Get
            Return m_tetangga
        End Get
        Set(value As List(Of Titik))
            m_tetangga = value
        End Set
    End Property

    Public Property bobot() As List(Of Integer)
        Get
            Return m_bobot
        End Get
        Set(value As List(Of Integer))
            m_bobot = value
        End Set
    End Property
End Class

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.