Wikipedia

Algoritma Floyd-Warshall: Perbedaan antara revisi

Jelajahi riwayat secara interaktif
← Revisi sebelumnya
Konten dihapus Konten ditambahkan
VisualTeks wiki
Ardiantapargo (bicara | kontrib)
40 suntingan
k definisi dan sejarah
Wadaihangit (bicara | kontrib)
18.665 suntingan
k Menambahkan foto ke halaman #WPWP
 
(8 revisi perantara oleh 8 pengguna tidak ditampilkan)
Baris 1:
{{terjemah|Inggris}}
[[Berkas:Floyd-Warshall-Algorithm-Problem.png|jmpl|Masalah-Algoritma-Floyd-Warshall]]
 
Algoritma'''Algoritme Floyd-Warshall''' adalah algoritmaalgoritme untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).
 
== Sejarah ==
AlgoritmaAlgoritme Floyd-Warshall merupakan sebuah contoh penerapan dari pemrograman dinamis yang diperkenalkan oleh Robert Floyd pada tahun 1962. Namun, pada dasarnya memiliki kesamaan dengan algoritmaalgoritme 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'''.▼
 
▲AlgoritmaAlgoritme Floyd Warshall juga dikenal dengan '''AlgoritmaAlgoritme Floyd''', '''AlgoritmaAlgoritme Roy-Warshall''', '''AlgoritmaAlgoritme Roy-Floyd''', dan '''algoritmaalgoritme WFI'''.
== Algoritma ==
 
== Algoritme ==
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''|<sup>3</sup>).▼
 
▲AlgoritmaAlgoritme 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. AlgoritmaAlgoritme ini menghitung bobot terkecil dari semua jalur yang menghubungkan sebuah pasangan titik, dan melakukannya sekaligus untuk semua pasangan titik. AlgoritmaAlgoritme ini berjalan dengan waktu Θ(|''V''|<sup>3</sup>).
Dasar algoritma ini adalah observasi berikut:▼
--belum diterjemahkan--
 
▲Dasar algoritmaalgoritme ini adalah observasi berikut:
Implementasi algoritma ini dalam pseudocode:
--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)
Baris 23 ⟶ 21:
'''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 algoritmaalgoritme''
'''for''' k '''from''' 1 '''to''' n
'''for''' i '''from''' 1 '''to''' n
Baris 40 ⟶ 38:
 
== Aplikasi dan Generalisasi ==
* Jalur terpendek dalam graf berarah (AlgoritmaAlgoritme Floyd).
* Perhitungan cepat untuk menemukan rute terpendek dalam jaringan.
 
== Implementasi ==
* Implementasi AlgoritmaAlgoritme Floyd-Warshall dalam [[Perl]], yaitu [http://search.cpan.org/~jhi/Graph-0.67/ Graph Module]
* Implementasi AlgoritmaAlgoritme Floyd-Warshall dalam [[JavascriptJavaScript]] di [http://alexle.net/stuff/floyd-algorithm/ Alex Le's Blog] {{Webarchive|url=https://web.archive.org/web/20080820050534/http://alexle.net/stuff/floyd-algorithm/ |date=2008-08-20 }}
 
== Referensi ==
 
* {{cite book|authorlink = Thomas H. Cormen|first=Thomas H.|last=Cormen|coauthors= [[Charles E. Leiserson|Leiserson, Charles E.]]; [[Ronald L. Rivest|Rivest, Ronald L.]]|title = [[Introduction to Algorithms]]|edition = first edition|publisher = MIT Press and McGraw-Hill|date = 1990|id = ISBN 0-262-03141-8 }}
** Section 26.2, "The Floyd-Warshall algorithm", pp. &nbsp;558–565;
** Section 26.4, "A general framework for solving path problems in directed graphs", pp. &nbsp;570–576.
* {{cite journal | first = Robert W. | last = Floyd | authorlink = Robert W. Floyd | title = Algorithm 97: Shortest Path | journal = [[Communications of the ACM]] | volume = 5 | issue = 6 | pages = 345 | date = June 1962 | id = {{doi|10.1145/367766.368168}} }}
* {{cite book|authorlink = Stephen Cole Kleene|first = S. C.|last = Kleene|chapter = Representation of events in nerve nets and finite automata|title = Automata Studies|editor = [[Claude Elwood Shannon|C. E. Shannon]] and [[John McCarthy (computer scientist)|J. McCarthy]]|pages = pp. 3–42|publisher = Princeton University Press|date = 1956 }}
Diperoleh dari "https://wiki-indonesia.club/wiki/Algoritma_Floyd-Warshall"