Apa yang anda ketahui tentang Algoritma Bellman-Ford?

Algoritma Bellman-Ford

Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah graf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu vertex.

Apa yang anda ketahui tentang Algoritma Bellman-Ford ?

image

Algoritma Bellman-ford adalah algoritma untuk menyelesaikan permasalahan lintasan terpendek dengan dengan sumber tunggal. Jadi algoritma Bellman-ford menghitung jarak terpendek (dari satu sumber) pada sebuah graf berbobot. Maksud dari sumber tunggal ialah bahwa algoritma menghitung semuah jarak terpendek yang berawal dari satu titik. Di samping itu algoritma ini menggunakan d[u] sebagai batas atas dengan jarak d[u,v] dari u ke v. Algoritma ini melakukan inisialisasi jarak titik sumber ke titik nol dan semua titik lainnya (sampai tak hingga). Secara progresif algoritma ini melakukan perbaikan (updating) jarak pada setiap titik sumber ke titik v di dalam V hingga dicapai lintasan dalil Boolean TRUE yaitu jika grafik mengandung lingkaran tidak negatif maka titik dapat dicapai dari titik sumber, dan dalam kondisi lain dikatakan Bollean FALSE. Algoritma Bellman ford sebagai berikut :
BELLMAN-FORD (G, w, s)

  1. INITIALIZE-SINGLE-SOURCE (G, s)
  2. for each vertex i = 1 to V[G] - 1 do
  3. for each edge (u, v) in E[G] do
  4. RELAX (u, v, w)
  5. For each edge (u, v) in E[G] do
  6. if d[u] + w(u, v) < d[v] then
  7. return FALSE
  8. return TRUE

Langkah-langkah algoritma Bellman-Ford
Algoritma Bellman-Ford menentukan lintasan terpendek Secara umum, langkah-langkah algoritmanya adalah sebagai berikut:

  1. Menentukan titik asal dan mendaftar semua titik maupun sisi

  2. Memberi nilai untuk titik asal sama dengan nol dan titik-titik lainnya dengan tak hingga.

  3. Memulai iterasi terhadap semua titik yang ada dimulai dengan titik asal. untuk menentukan jarak dari semua titik yang berhubungan dengan titik asal dengan formula seperti berikut :
    U = titik asal
    V = titik tujuan
    UV = sisi yang menghubungkan U dan V,
    Jika jarak V lebih besar dari jarak U+bobot UV maka jarak V diisi dengan jarak U+bobot UV, dilakukan hingga semua titik terjelajahi.

  4. Melakukan iterasi untuk semua sisi yang ada untuk mengecek apakah ada siklus negatif dalam graf tersebut

Kompsleksitas Waktu algoritma Bellman-Ford
Secara kompleksitas waktu, algoritma ini hanya memiliki 1 kemungkinan, yaitu dengan notasi Big-O diberikan O(V·E). V adalah jumlah titik graf berbobot, lalu E adalah jumlah sisi dalam graf. Oleh sebab itu untuk jumlah sisi ataupun titik yang sangat besar akan menyebabkan algoritma ini akan berjalan lebih lama dibandingkan algoritma Dijkstra.
Berikut penjabaran perhitungan kompleksitas waktu.

  1. Tahap inisialisasi mempunyai kompleksitas O(V). Maksudnya bahwa, jika n banyaknya titik maka inisialisasi dilkukan sebanyak n dengan titik asal 0 dilakukan satu kali dan titik yang lainnya (n1).
  2. Tahap kedua yaitu melakukan pencarian jalur atau jalan terpendek terhadap suatu titik s mempunyai kompleksitas O(V.E). Hal ini karena perulangan untuk tahap pencarian ada dua kali, perulangan pertama sebanyak O(E), selanjutnya O(E) diulanga sebanyak O(V) jadi totalnya adalah O(V.E)
  3. Tahap ketiga yaitu pengecekan ada atau tidaknya sisi negative pada jalur, mempunyai kompleksitas O(E).