algoritma floyd warshall dengan siklus negatif
TRANSCRIPT
![Page 1: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/1.jpg)
ALGORITMA FLOYD-
WARSHALL DENGAN
SIKLUS NEGATIF Fajar Maulana Putra [5109100057]
Ahmad Yusuf Syaifuddin [5109100134]
Agus Budi Raharjo [5109100164]
Adam [5109100702]
![Page 2: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/2.jpg)
PENDAHULUAN
Algoritma Floyd Warshall adalah algoritma
untuk mencari jarak terpendek dari semua
simpul dalam graf
Hanya bisa untuk graf tanpa siklus negatif,
namun bisa mendeteksi keberadaan siklus
negatif dalam graf
![Page 3: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/3.jpg)
PENELITIAN SEBELUMNYA
Banyak peneliti yang sudah menemukan
alternatif algoritma Floyd Warshall, diantaranya
: Michael L. Fredman, New bounds on the complexity of the shortest
path problem, SIAM Journal on Computing 5 (1) (1976) 83–89.
Tadao Takaoka, A new upper bound on the complexity of the all pairs
shortest path problem, Information Processing Letters 43 (1992) 195–
199.
Yijie Han, A note of an O(n3 / log n) time algorithm for all pairs
shortest paths, Information Processing Letters 105 (2008) 114–116
Tadao Takaoka, A faster algorithm for the all-pairs shortest path
problem and its application, in: K.-Y. Chwa, J.I. Munro (Eds.),
COCOON 2004, in: Lecture Notes in Computer Science, vol. 3106,
SpringerVerlag, Berlin–Heidelberg, 2004, pp. 278–289.
Uri Zwick, A slightly improved sub-cubic algorithm for the all pairs
shortest paths problem with real edge lengths, Algorithmica 46 (2006)
181–192.
![Page 4: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/4.jpg)
Tadao Takaoka, An O(n3 log log n / log n) time algorithm for the
allpairs shortest path problem, Information Processing Letters
96(2005) 155–161.
Timothy M. Chan, All-pairs shortest paths with real weights in O(n3 /
log n) time, Algorithmica 50 (2008) 236–243.
Yijie Han, An O(n3(log log n / log n)5/4) time algorithm for all pairs
shortest paths, Algorithmica 51 (2008) 428–434.
Timothy M. Chan, More algorithms for all-pairs shortest paths in
weighted graphs, in: STOC’07, 2007, pp. 590–598.
Yijie Han, An O(n3 log log n/ log2n) time algorithm for all pairs
shortest paths, Manuscript, 2009.
Akan tetapi, algoritma-algoritma di atas jauh lebih
rumit dan seringkali melibatkan struktur data yang
kompleks, sehingga dalam banyak kasus algoritma
Floyd Warshall tetap menjadi pilihan
![Page 5: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/5.jpg)
TUJUAN
Tujuan Stefan Hougardy membuat paper ini
adalah untuk menunjukkan bahwa untuk
algoritma Floyd Warshall yang standar, terdapat
contoh sederhana (dengan siklus negatif) yang
bisa menyebabkan overflow
![Page 6: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/6.jpg)
MASUKAN
Sebuah graf berarah G dimana G boleh memiliki
siklus negatif
Contoh graf berarah dengan siklus negatif
![Page 7: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/7.jpg)
METODE PENELITIAN
Algoritma Floyd Warshall
Masukan: Sebuah graf berarah G dengan V(G) ={1,...,n} dan bobot c : E(G) → R
Keluaran: Sebuah matriks M berukuran n x n dimana M[i, j] berisi jarak terpendek dari simpul i ke simpul j.
1. M[i,j] := ∞ ∀i ≠ j
2. M[i,i] := 0 ∀i
3. M[i,j] := c((i,j)) ∀(i,j) ∈ E(G)
4. for i := 1 to n do
5. for j := 1 to n do
6. for k := 1 to n do
7. if M[j,k] > (M[j,i]+M[i,k]) then
8. M[j,k] := M[j,i] + M[i,k]
9. for i := 1 to n do
10. if M [i,i] < 0 then return (‘graf memiliki siklus negatif’)
![Page 8: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/8.jpg)
Dari deskirpsi masukan diatas, kita memisalkan
cmax sebagai nilai mutlak terbesar dari sebuah
sisi dalam graf, atau bisa ditulis
cmax := maxe ∈ E(G) {|c(e)|}
║M║max adalah norma maksimum dari matriks M dengan mengabaikan nilai ∞,atau bisa ditulis
:
║M║max := maxi,j{|M[i,j]| dimana M[i,j] ≠ ∞}
![Page 9: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/9.jpg)
Dari fakta diatas menghasilkan proposisi
berikut:
Jika masukan pada Algoritma Floyd Warshall
tidak memiliki siklus negatif, maka ║M║max ≤
n.cmax selama eksekusi algoritma
Bukti : Jika tidak ada siklus negatif, maka selama algoritma bekerja, M[i,j] ≠ ∞ berisi jarak
dari simpul i ke simpul j. Dengan demikian
sebuah path bisa berisi paling banyak n-1 sisi
dari hasil akhir
![Page 10: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/10.jpg)
Sekarang akan dibuktikan bahwa entry dari matriks
M bisa membesar secara eksponensial jika masukan
berisi siklus negatif, diberikan teorema berikut :
Terdapat sebuah graf dimana
║M║ max = 2 · 6n-1· cmax
selama eksekusi Algoritma Floyd Warshall.
Bukti : misalkan ada graf dengan simpul 1…n dan
himpunan sisi E = {(1,i) | 1 ≤ i ≤ n} U {(I,1) | 2 ≤ i ≤ n}.
Berikan c(e) = -1 untuk semua e ∈ E
Contoh matriks dan penyelesaian
![Page 11: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/11.jpg)
![Page 12: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/12.jpg)
![Page 13: Algoritma floyd warshall dengan siklus negatif](https://reader033.vdokumen.com/reader033/viewer/2022061510/558c3cf3d8b42acb028b4784/html5/thumbnails/13.jpg)
HASIL PENELITIAN
Hasil dari penelitian yang dilakukan oleh Stefan
Hougardy adalah kebenaran teorema berikut :
Terdapat sebuah graf dimana
║M║ max = 2 · 6n-1· cmax
selama eksekusi Algoritma Floyd Warshall.