Algoritma Warshall dan Bellman
1. Algoritma Floyd-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);
pengertian dari 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. Algoritma ini berjalan dengan waktu Θ(|V|3).
Implementasi algoritma ini dalam pseudocode: (Graf direpresentasikan sebagai matrix keterhubungan, yang isinya ialah bobot/jarak sisi yang menghubungkan tiap pasangan titik, dilambangkan dengan indeks baris dan kolom) (Ketiadaan sisi yang menghubungkan sebuah pasangan dilambangkan dengan Tak-hingga)
function fw( int [1..n,1..n] graph) { // Inisialisasi var int [1..n,1..n] jarak := graph var int [1..n,1..n] sebelum for i from 1 to n for j from 1 to n if jarak[i,j] jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] + jarak[k,j] sebelum[i,j] = sebelum[k,j] return jarak }
2. Algoritma Bellman-Ford
Algoritma Bellman-Ford menyelesaikan masalah garis terpendek single-source untuk grafik dengan dua simpul(node) positive and negative. Jika kamu hanya membutuhkan untuk menyelesaikan masalah jalur terpendek untuk node positive, Algoritma Dijkstra memberikN lternatif yg lebih efisien. Jika semua node sama BFS adalah alternative yang lebih efisien.
Sebelum memanggil fungsi bellman_ford_shortest_paths(),user harus menentukan puncak/root-nya dengan nilai 0 atau ∞ tergantung user ingin memulai dengan node pertama yang mana. Algoritma Bellman-Ford memproses dengan looping semua node di grafik, menggunakan operasi relaksasi untuk setiap node. Pada pseucode di bawah ini, v adalah puncak/root untuk u, w peta node, dan d adalah panjang peta yang merekam panjang dari jalur terpendek untuk setiap node. Jika p adalah prosesor yang telah direkam untuk parent dari setiap node, maka akan menjadi parent dari pohon tersebut.
RELAX(u, v, w, d, p)
if (w(u,v) + d[u] <>
d[v] := w(u,v) + d[u]
p[v] := u
else
…
relax edge (u,v)
edge (u,v) is not relaxed
Algoritma akan mengulang loop |V| kali setelah dijamin bahwa panjang dari setiap node telah ditentukan kemungkinan minimum kalau grafik adalah rute negative. Jika grafik adalah route negative, maka node di grafik tidak dapat di minimaliskan. Dalam grafik aka nada node (u,v) seperti w(u,v) + d[u] <>
BELLMAN-FORD(G)
// Optional initialization
for setiap root u di V
d[u] := infinity
p[u] := u
end for
for i := 1 to |V|-1
for setiap node (u,v) di E
RELAX(u, v, w, d, p)
end for
end for
for setiap node (u,v) di E
if (w(u,v) + d[u] <>
return (false, , )
else
…
end for
return (true, p, d)
Node uji (u,v)
node (u,v) tidak diminimalis
node (u,v) diminimalis
Ada dua pilihan utama untuk memperoleh output dari fungsi Bellman. Jika user memberikan jarak peta melalui parameter distance_map() kemudian jarak yang paling pendek dari node utama untuk setiap root di grafik akan direkam dip peta jarak (diberikan jika fungsi bernilai true). Pilihan kedua adalah merekam jalur pohon terpendek di predecessor_map(). Untuk setiap root u di V, p[u] akan menjadi predesesor dari u di jarak terpendek pohon (kalau tidak p[u] = u, pada kasus u adalah root utama).Pada dua pilihan tersebut, user dapat memberikan pengunjung buatan sendiri yang dapat mengambil aksi pada setiap poin dari kebanyakan algoritma.
pengertian dari Wikipedia :
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.
Algoritma Bellman-Ford menggunakan waktu sebesar O(V.E), di mana V dan E adalah banyaknya sisi dan titik.
Tidak ada komentar:
Posting Komentar