Algoritma Floyd -Warshall
Pengertian Algoritma Floyd - Warshall :
Algoritma Floyd - Warshall merupakan salah satu varian dari pemrograman dinamis, yaitu suatu mode 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.
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.
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 ini membedakan pencarian solusi menggunakan pemrograman dinamis (warshall) dengan algoritma greedy adalah, bahwa keputusan yang diambil pada tiap tahap pada algoritma greedyhanya berdasarkan 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 sesuatu keputusan pada suatu tahap. Dalam beberapa kasus, algoritma greedy gagal memberikansolusi terbaik karena kelemahan yang dimilikinya tadi. Disinilah 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 pengambilan 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 dari penggunaan fungsi ini adalah untuk mencari jalur terpendek dari setiap simpul i ke simpul j dengan perantara simpul 1 s.d k+1.
- 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 pengambilan 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 dari penggunaan fungsi ini adalah untuk mencari jalur terpendek dari setiap simpul i ke simpul j dengan perantara simpul 1 s.d k+1.
Tidak ada komentar:
Posting Komentar