Algoritma Floyd - Warshall

Pengertian Algoritma Floyd-Warshall

- Pengertian Umum : Merupakan 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.

- Pengertian Wikipedia : Algoritma Floyd-Warshall memiliki input graf berarah dan berbobot (V,E), yang berupa daftar titik (node/vertex V) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah jalur adalah bobot jalur tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik.


Definisi Strategi Algoritma Floyd Warshall

Hal yang membedakan pencarian solusi menggunakan pemrograman dinamis (Warshall) dengan algoritma greedy adalah, bahwa keputusan yang diambil pada tiap tahap pada algoritma greedy hanya berdasarkan pada informasi yang terbatas, sehingga hanya 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. Dalam beberapa kasus, Algoritma Greedy gagal memberikan solusi terbaik karena kelemahan yang dimilikinya tadi. Di sinilah peran pemrograman dinamis yang mencoba untuk memberikan solusi yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari pengambilan keputusan pada suatu tahap.

Pemrograman dinamis mampu :

• Mengurangi pengenumerasian (Pendaftaran) keputusan yang tidak mengarah ke solusi.

• Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal.


Analisis Algoritma Floyd-Warshall

Algoritma Floyd-Warshall membandingkan semua kemungkinan lintasan pada graf untuk setiap sisi dari semua simpul. Hal tersebut bisa terjadi karena adanya perkiraan pengambilkan keputusan (pemilihan jalur terpendek) pada setiap tahap antara dua simpul, hingga perkiraan tersebut diketahui sebagai nilai optimal. Misalkan terdapat suatu graf G dengan simpul-simpul V yang masing-masing bernomor 1 s.d. N (sebanyak N buah). Misalkan pula terdapat suatu fungsi shortestPath(i, j, k) yang mengembalikan kemungkinan jalur terpendek dari i ke j dengan hanya memanfaatkan simpul 1 s.d. k sebagai titik perantara. Tujuan akhir penggunaan fungsi ini adalah untuk mencari jalur terpendek dari setiap simpul i ke simpul j dengan perantara simpul 1 s.d. k+1.

Ada dua kemungkinan yang terjadi:

• Jalur terpendek yang sebenarnya hanya berasal darisimpul-simpul yang berada antara 1 hingga k.
• Ada sebagian jalur yang berasal dari simpul-simpul i s.d. k+1, dan juga dari k+1 hingga j.

Contoh Kasus Algoritma Floyd-Warshall

Ada beberapa jalur antara A dan E:
Path 1 : A -> B -> E 20
Path 2 : A -> D -> E 25
Path 3 : A -> B -> D -> E 35
Path 4 : A -> D -> B -> E 20




Ada beberapa hal yang harus dilihat
di grafik tersebut :

• Ada bisa lebih dari satu rute antara dua node.
• Jumlah node dalam rute tersebut tidak penting (Jalur 4 memiliki 4 node tetapi lebih pendek dari Jalur 2, yang memiliki 3 node).
• Ada bisa lebih dari satu jalur panjang minimal.






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 menghasilkan jarak tempuh yang lebih panjang.


Kesimpulan

• Algoritma Floyd-Warshall yang menerapkan pemrograman dinamis lebih menjamin keberhasilan penemuan solusi optimum untuk kasus penentuan lintasan terpendek (single pair shortest path).
• Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal.