 | Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa Inggris. Jika halaman ini ditujukan untuk komunitas bahasa Inggris, halaman itu harus dikontribusikan ke Wikipedia bahasa Inggris. Lihat daftar bahasa Wikipedia. Artikel yang sama sekali tidak diterjemahkan dapat dihapus secara cepat sesuai kriteria A2. Jika Anda ingin memeriksa artikel ini, Anda boleh menggunakan mesin penerjemah. Namun ingat, mohon tidak menyalin hasil terjemahan tersebut ke artikel, karena umumnya merupakan terjemahan berkualitas rendah. |
Algoritma Floyd-Warshall adalah algoritma untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).
Sejarah
Algoritma Floyd-Warshall merupakan sebuah contoh penerapan dari pemrograman dinamis yang diperkenalkan oleh Robert Floyd pada tahun 1962. Namun, pada dasarnya memiliki kesamaan dengan algoritma yang pernah diperkenalkan sebelumnya oleh Bernard Roy pada tahun 1959 dan juga Stephen Warshall pada 1962.
Algoritma Floyd Warshall juga dikenal dengan Algoritma Floyd, Algoritma Roy-Warshall, Algoritma Roy-Floyd, dan algoritma WFI.
Algoritma
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 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).
Dasar algoritma ini adalah observasi berikut:
--belum diterjemahkan—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] < Tak-hingga
sebelum[i,j]:= i
// Perulangan utama pada algoritma
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 (Algoritma Floyd).
- Perhitungan cepat untuk menemukan rute terpendek dalam jaringan.
Implementasi
- Implementasi Algoritma Floyd-Warshall dalam Perl, yaitu Graph Module
- Implementasi Algoritma 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 first edition). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
{{cite book}}:|edition=memiliki teks tambahan; Parameter tidak dikenal|coauthors=diabaikan (|author=disarankan)- 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. (Juni 1962). "Algorithm 97: Shortest Path". Communications of the ACM. 5 (6): 345. DOI:10.1145/367766.368168.
{{cite journal}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link) - Kleene, S. C. (1956). "Representation of events in nerve nets and finite automata". Dalam C. E. Shannon and J. McCarthy (ed.). Automata Studies. Princeton University Press. hlm. pp. 3–42.
{{cite book}}:|pages=memiliki teks tambahan - Warshall, Stephen (Januari 1962). "A theorem on Boolean matrices". Journal of the ACM. 9 (1): 11–12. DOI:10.1145/321105.321107.
{{cite journal}}: Pemeliharaan CS1: Tanggal diterjemahkan otomatis (link)