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

Titik awalTitik TujuanJarak
Titik ATitik B6
Titik ATitik E7
Titik BTitik C5
Titik BTitik D-4
Titik BTitik E8
Titik CTitik B-2
Titik DTitik C7
Titik ETitik C-3
Titik ETitik D9

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
bellman ford awal

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)

cmd16b

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

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.


Tinggalkan Balasan ke pip Batalkan balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

7 pemikiran di “Algoritma Bellman-Ford

  • firman

    kenapa bobot bisa negatif? kalo saya pahamin dijkstra ga ada bobot nagatif, nah dari mana bobot bisa negatif di bellman ford?
    (anggep studi kasus google maps, apa yg dimaksud bobot negatid adalah dari titik A ke B trus B ke A lagi bolak balik itu bobot negatif?)

    • pip Penulis

      Anda perlu pahami bahwa implementasi kasus untuk masing-masing topik adalah berbeda. Dalam contoh kasus ini saya menggunakan nilai jarak yang dapat berupa nilai negatif, sedangkan dalam cuplikan topik anda sepertinya nilai jarak tidak dapat bernilai negatif. Akan tetapi yang perlu anda perhatikan disini adalah nilai bobotnya. Nilai bobot tidak sama dengan jarak. Algoritma ini akan mencari nilai bobot dari masing-masing jarak, dan kemudian mencari jalur terbaik berdasarkan nilai bobot tersebut. Acuan yang digunakan adalah sudah tidak lagi menggunakan jarak.

  • Harison

    Terima kasih pak admin piptools.net, aplikasinya sangat membantu, bisakah saya mendapatkan source code aplikasi ini? Download link yg ada mengarah ke aplikasi algoritma BFS, bukan Bellman-Ford, terima kasih sebelumnya.