Tugas Jarkom 4 Algoritma Shorthest Path

1.Bellman-Ford

Mencari jalur terpendek antara 1 source node ke titik-titik lainnya didalam jaringan.

—Jarak dapat positif atau negatif.

—Diasumsikan tidak ada cycle dengan jarak negatif.

—di,j = ∞, jika (i,j) bukan arc dari graph.

—Didalam algoritma B-F, yang dicari mula-mula adalah.

Jarak terpendek dengan maksimum 1 arc.

Jarak terpendek dengan maksimum 2 arc, dst.

Jarak terpendek dengan maksimum h arc.

à SHORTEST (≤ h) path.

—Di(h) adalah jalur terpendek (≤h) dari node 1 (source node) ke node I

—= 0, untuk semua h

—Start : Di(0) = ∞, untuk semua I ≠ 1.

—Untuk setiap successive h ≥ 0,

Di(h+1) = minj[Dj(h) + dji], untuk semua I ≠ 1

—

—jumlah step maks = |N| - 1

—dij = jarak dari source i ke destination j

—

—dij = 0 ® i=j

—dij = ~ ® i ≠ j

—dij = 0 ® i=j

2.Algoritma Dijkstra

—Complexity algoritma Dijkstra = Φ(N2).

—Semua jarak d/p arc harus positif.

—Terdapat 1 set node P.

—Mencari jalur terpendek dari node 1 (source node) ke setiap node lainnya didalam graph.

—Estimasi jalur terpendek di update setiap kali, dan jika estimasi sudah mencapai actual distance, masukkan node dalam set P.

—Kondisi mula:

P = {1}, D1 = 0, Dj = dij, j ≠ 1

—Step 1: Untuk setiap i* € P,

dimana: Di* = min Dj ; j € P

set P = P U{i*}; jika P = N à stop, else

—Step 2: Update Dj untuk j € P

Dj = min[Dj, Di* + di*j]

Kembali ke step 1.

3. Algoritma Floyd-Warshall

— Mencari jalur terpendek diantara semua pasangan node secara bersama-sama —Jarak arc dapat positif atau negatif, tetapi tidak ada cycle dengan jarak negatif —Algoritma F-W melakukan iterasi pada set node, yang diperbolehkan sebaga intermediate nodes (titik-titik antara) didalam graph —Start dengan arc tunggal (tanpa intermediate nodes) —Selanjutnya jarak terpendek dihitung dengan batasan hanya node 1 (asumsi sebagai souce node) yang dapat digunakan sebagai intermediate node, diteruskan dengan batasan bahwa hanya node 1 dan node 2 yang dapat digunakan sebagai intermediate node, dst.

—Definisi : Dij(n) = jalur terpendek antara node i dan node j dengan batasan (ketentuan) bahwa hanya node 1,2,…..,n yang dapat digunakan sebagai intermediate nodes —Step (1): Start à Dij(0) = dij, untuk semua i,j; i≠j —Step (2): Untuk n=0,1,…,N-1 Dij(n+1) = min [Dij(n),Di(n+1)(n) + D(n+1)j(n)] untuk semua i≠j dst. Algoritma stop setelah n = N – 1, dimana N = jumlah node dalam jaringan —Kompleksitas algoritma F-W adalah Φ(N3) àkarena N step dalam algoritma F-W harus dieksekusi untuk setiap node. = jika algoritma Dijkstra diulang untuk setiap pilihan yang mungkin untuk source node.

4.Distance Vector Algorithm

ada semua node,X: Inisialisasi Untuk semua node bersebelahan v DX(*,v) = ∞ {* berarti untuk semua baris} DX(v,v) = c(X,v) Untuk semua tujuan, y Kirim minwXD (y,w) kesetiap tetangga loop tunggu (sampai ada perubahan cost link ke tetangga V atau diterima update dari tetangga V) If (c(X,V) berubah dengan d) 10. then untuk semua tujuan y: DX(y,V) = DX(y,V) + d 11. Else if (diterima update dari V dengan tujuan Y) 12. then untuk tujuan tunggal y: DX(Y,V) = c(X,V) + nilai baru 13. IF ada nilai baru minwDX(Y,w) untuk semua tujuan Y 14. then kirim nilai baru minwDX(Y,w) ke semua tetangga 15.terus menerus