Algoritma Bellman-Ford
// 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”
Kompleksitas waktu algoritma (Running
time)
Algoritma Bellman-Ford menggunakan waktu
sebesar O(V.E), di mana V dan E adalah
banyaknya sisi dan titik.
Inisialisasi: O(v)
Loop utama: O(v.e)
Pengecekan loop negative: O(e)
Total: O(v.e)
Algoritma Floyd-Warshall
function fw(int[1..n,1..n] graph) {
// Inisialisasi
var int[1..n,1..n] jarak := graph
var int[1..n,1..n] sebelum
for i from 1 to n
for j from 1 to n
if jarak[i,j] < Tak-hingga
sebelum[i,j] := i
// Perulangan utama pada algoritma
for k from 1 to n
for i from 1 to n
for j from 1 to n
if jarak[i,j] > jarak[i,k] + jarak[k,j]
jarak[i,j] = jarak[i,k] + jarak[k,j]
sebelum[i,j] = sebelum[k,j]
return jarak
}
Kompleksitas waktu algoritma (Running
time)
Algoritma ini berjalan dengan waktu O(V3).
Kesimpulan
Kesimpulan yang dapat dimbil dari studi ini
adalah:
1. Urutan algoritma penyelesaian persoalan
lintasan terpendek berdasarkan kompleksitas
algoritmanya adalah
O(V.E)<O((E+V)logV) <O(V3)=Bellman-
Ford<Dijkstra<Floyd-Warshall
2. Algoritma Bellman-Ford dapat menangani
masalah lintasan terpendek dengan kasus graf
berbobot negatif yang tidak dapat diselesaikan
oleh algoritma Dijkstra.
3. Berdasarkan masalah yang dapat diselesaikan.
* Algoritma Bellman-Ford untuk masalah
Single-source Shortest Path.
* Algoritma Floyd-Warshall untuk masalah Allpairs
Shortest Path
Tinggalkan sebuah Komentar
Belum ada komentar.
Komentar RSS Lacak Balik URI Pengenal
