Algoritma Bellman–Ford

Contoh algoritma Bellman – Ford yang digunakan pada graf 5 titik

Algoritma Bellman–Ford menghitung jarak terpendek (dari satu sumber) pada sebuah digraf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritme Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif.

Algoritma Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah banyaknya sisi dan titik.

Dalam konteks ini, bobot ekivalen dengan jarak dalam sebuah sisi. 

// Definisi tipe data dalam graf
record titik {
    list sisi2
    real jarak
    titik sebelum
}
record sisi {
    titik dari
    titik ke
    real bobot
}

function BellmanFord(list semuatitik, list semuasisi, titik dari)
   // Argumennya ialah graf, dengan bentuk daftar titik  
   // and sisi. Algoritma ini mengubah titik-titik dalam 
   // semuatitik sehingga atribut jarak dan sebelum 
   // menyimpan jarak terpendek.

   // Persiapan
   for each titik v in semuatitik:
       if v is dari then v.jarak = 0
       else v.jarak:= tak-hingga
       v.sebelum:= null
   
   // Perulangan relaksasi sisi
   for i from 1 to size(semuatitik):
       for each sisi uv in semuasisi:
           u:= uv.dari
           v:= uv.ke             // uv adalah sisi dari u ke v
           if v.jarak > u.jarak + uv.bobot
               v.jarak:= u.jarak + uv.bobot
               v.sebelum:= u

   // Cari sirkuit berbobot(jarak) negatif
   for each sisi uv in semuasisi:
       u:= uv.dari
       v:= uv.ke
       if v.jarak > u.jarak + uv.bobot
           error "Graph mengandung siklus berbobot total negatif"

Secara umum coding algoritma dapat juga menggunakan teknik coding pemrograman yang lain.

Ikon rintisan

Artikel bertopik komputer ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.