ALGORITMA WARSHALL

Algoritma floyd-warshall adalah satu varian dari pemrograman dinamis,yaitu dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Sehingga solusi solusi tersebut terbentuk dari solusi yang berasal dari tahap seblumnya.Algoritma warshall ini berbeda dengan algoritma greedy.karena algoritma greedy tidak diperhatikan konsekuensi yang akan terjadi seandainya kita memilih suatu keputusan pada suatu tahap. Algoritma warshall disebut juga algoritma dinamis.

karakteristik dari algoritma dinamis ialah :

1. persoalannya dibagi atas beberapa tahap,yang setiap tahapnya diambil satu keputusan.

2. Masing-masing tahap terdiri dari sejumlah status yang saling berhubungan.

3. Hasil keputusan akan di transformasikan.

4. Ongkos tergantung dari ongkos tahapan yang telah berjalan dan ongkos pada tahap itu sendiri.

5. Keputusan terbaik pada tahap bersifat independen.

6. Terdapat hubungan rekursif yang menyatakan bahwa keputusan terbaik dalam setiap status pada tahap -k.

Pada algoritma ini dilakukan pendekatan ,yaitu pendekatan maju dan pendekatan mundur.

Analisisnya :

Melakukan perbandingan terlebih dahulu,yaitu pada tiap tahap antara 2 simpul hingga perkiraan tersebut diketahui sebagai nilai optimal. Ada 2 kemungkinan yang terjadi jika kita mencari jalur terpendek (shortest path) dari setiap i ke simpul j dan perantara simpul 1 s.d ke k+1,

1. Jalur terpendek hanya berasal dari simpul yang berada antara 1 hingga k.

2. Ada sebagian jalur yang berasal dari simpul 1 s/d k+1 dan juga dari k+1 hingga i.

Maka dari itu rumus fungsi shortest path dengan algoritma ini ;

basis -0

shortest path(i,j,0)=edgecost(i,j);

rekurens

shortest path (i,j,k) = min(shortestpath (i,,j,k-1),shortestpath(i,k,k-1)+shortestpath(k,j,k-1);