Algoritma Floyd-Warshall
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b2/Floyd-Warshall-Algorithm-Problem.png/220px-Floyd-Warshall-Algorithm-Problem.png)
Algoritme Floyd-Warshall adalah algoritme untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).
Sejarah
Algoritme Floyd-Warshall merupakan sebuah contoh penerapan dari pemrograman dinamis yang diperkenalkan oleh Robert Floyd pada tahun 1962. Namun, pada dasarnya memiliki kesamaan dengan algoritme yang pernah diperkenalkan sebelumnya oleh Bernard Roy pada tahun 1959 dan juga Stephen Warshall pada 1962.
Algoritme Floyd Warshall juga dikenal dengan Algoritme Floyd, Algoritme Roy-Warshall, Algoritme Roy-Floyd, dan algoritme WFI.
Algoritme
Algoritme 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 memiliki siklus dengan bobot negatif. Algoritme ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. Algoritme ini berjalan dengan waktu Θ(|V|3).
Dasar algoritme ini adalah observasi berikut:
--belum diterjemahkan—Implementasi algoritme 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] < Tak-hingga sebelum[i,j]:= i // Perulangan utama pada algoritme for k from 1 to n 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 }
Aplikasi dan Generalisasi
- Jalur terpendek dalam graf berarah (Algoritme Floyd).
- Perhitungan cepat untuk menemukan rute terpendek dalam jaringan.
Implementasi
- Implementasi Algoritme Floyd-Warshall dalam Perl, yaitu Graph Module
- Implementasi Algoritme Floyd-Warshall dalam JavaScript di Alex Le's Blog Diarsipkan 2008-08-20 di Wayback Machine.
Referensi
- Cormen, Thomas H. (1990). Introduction to Algorithms (edisi ke-first edition). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Parameter
|coauthors=
yang tidak diketahui mengabaikan (|author=
yang disarankan) (bantuan)Pemeliharaan CS1: Teks tambahan (link)- Section 26.2, "The Floyd-Warshall algorithm", pp. 558–565;
- Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
- Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345. DOI:10.1145/367766.368168.
- Kleene, S. C. (1956). "Representation of events in nerve nets and finite automata". Dalam C. E. Shannon and J. McCarthy. Automata Studies. Princeton University Press. hlm. pp. 3–42. Pemeliharaan CS1: Teks tambahan (link)
- Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM. 9 (1): 11–12. DOI:10.1145/321105.321107.
Pranala luar
- Interactive animation of Floyd-Warshall algorithm