![Algoritma Floyd Warshall Dan Bellman Ford [PDF]](https://pdfs.asia/img/200x200/algoritma-floyd-warshall-dan-bellman-ford.jpg)
4 0 973 KB
Algoritma Bellman-Ford dan Floyd-Warshall
Algoritma Bellman-Ford • 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. Algoritma 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.
Bellman-Ford 1
0
Disini kita akan menghitung jarak terpendek (shortest path) dari atas hingga bawah.
8
6 4 -3
99
4 99
-4
3
5 -8
99
-5
2
99
-3
99
-2
3
99
-2
99
1
-4
5 99
99
4
Bellman-Ford 2
0
8
6 4 -3
6
4 4
-4
3
5 -8
99
-5
2
8
-3
99
-2
3
99
-2
99
1
-4
5 99
99
4
Pertama kita lihat bahwa untuk langkah pertama terdapat tiga pilihan, yaitu melalui jalur 6, 4, dan 8. Disini meskipun yang terkecil adalah empat, tetapi dalam algoritma Bellman-Ford memperhatikan juga solusi totalnya dan memperhatikan juga jalur negatif yang akan dilalui, sehingga jalur 6 dipilih karena kemudian hasilnya akan lebih sedikit dibanding jalur 4.
Bellman-Ford 3
0
Langkah kedua kita pilih jalur -3 karena hasilnya akan lebih sedikit dibanding jika kita memilih jalur 3.
8
6 4 -3
6
4 3
-4
3
5 -8
9
-5
2
8
-3 5
-2
3
99
-2
99
1
-4
5 99
99
4
Bellman-Ford 4
0
8
6 4 -3
6
4 3
-4
3
5 -8
-1
-5
2
8
-3 8
-2
3
-5
-2
99
1
-4
5 99
99
4
Berikutnya kita pilih jalur -4, sehingga sampai saat ini hasilnya adalah -1, paling sedikit dibanding jika kita memilih jalur-jalur yang lain.
Bellman-Ford 5
0
Selanjutnya kita pilih jalur -5 sehingga hasilnya akan lebih sedikit lagi yaitu -6.
8
6 4 -3
6
4 3
-4
3
5 -8
-1
-5
2
8
-3 8
-2
3
-6
-2
1
1
-4
5 99
11
4
Bellman-Ford 6
0
8
6 4 -3
6
4 3
-4
3
5 -8
-1
-5
2
8
-3 8
-2
3
-6
-2
-8
1
-4
5 -6
-10
4
Disini terdapat dua pilihan yaitu melalui jalur -2 atau -4, meskipun kita lihat -4 lebih sedikit dan akan menghasilkan hasil yang lebih kecil dibanding jika kita memilih -2, namun perlu kita perhatikan langkah selanjutnya, pada jalur 4,setelah kita melewatinya akan terdapat penjumlahan dengan 4 sehingga menghasilkan hasil akhir yaitu -6, sedangkan pada jalur -2, setelah kita melewatinya, akan terdapat penjumlahan dengan 1 sehingga hasilnya adalah -7 jelas lebih kecil dibanding jalur yang lain.
Bellman-Ford 7
0
Inilah hasil akhir dari algoritma Bellman-Ford.
8
6 4 -3
6
4 3
-4
3
5 -8
-1
-5
2
8
-3 8
-2
3
-6
-2
-8
1
-4
5 -7
-10
4
Floyd-Warshall • Algoritma Floyd-Warshall adalah salah satu varian dari pemrograman dinamis, yaitu suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu.
Floyd-Warshall • Hal yang membedakan pencarian solusi menggunakan pemrograman dinamis dengan algoritma greedy adalah bahwa keputusan yang diambil pada tiap tahap pada algoritma greedy hanya berdasarkan pada informasi yang terbatas sehingga nilai optimum yang diperoleh pada saat itu Jadi pada algoritma greedy, kita tidak memikirkan konsekuensi yang akan terjadi seandainya kita memilih suatu keputusan pada suatu tahap.
Floyd-Warshall D
15 km
20 km
G 20 km
26 km
25 km 15 km
B
A
E
60 km 23 km
H 28 km
F
30 km
C
42 km Pada algoritma ini diperhatikan agar hasil akhir adalah se-optimum mungkin. Pada jarak antar kota di atas, dari kota A untuk menuju kota F terdapat beberapa jalur, dapat melalui kota B terlebih dahulu, kota E, atau kota C. Pada algoritma ini dipilih jalur melalui kota C kemudian ke kota F sehingga jarak tempuh total adalah 72 km. Berbeda jika kita memilih kota B atau E terlebih dahulu, karena akan menhasilkan jarak tempuh yang lebih panjang.
