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 awal Titik Tujuan Jarak
Titik A Titik B 6
Titik A Titik E 7
Titik B Titik C 5
Titik B Titik D -4
Titik B Titik E 8
Titik C Titik B -2
Titik D Titik C 7
Titik E Titik C -3
Titik E Titik D 9

Contoh data awal adalah sebagai berikut:

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)

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

1b. Beri nilai awal jarak pada titik awal dengan 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)

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

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

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

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

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

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

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


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 sebuah komentar

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.