Algoritma Floyd-Warshall: Perbedaan antara revisi

AlgoritmaAlgoritme Floyd-Warshall adalah algoritmaalgoritme untuk mencari lintasan terpendek pada sebuah graf berbobot dengan bobot positif atau negatif (namun tidak memiliki siklus negatif).

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.

AlgoritmaAlgoritme Floyd Warshall juga dikenal dengan '''AlgoritmaAlgoritme Floyd''', '''AlgoritmaAlgoritme Roy-Warshall''', '''AlgoritmaAlgoritme Roy-Floyd''', dan '''algoritmaalgoritme WFI'''.

== AlgoritmaAlgoritme ==

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''|³).

Dasar algoritmaalgoritme ini adalah observasi berikut:

Implementasi algoritmaalgoritme ini dalam pseudocode:

''// Perulangan utama pada algoritmaalgoritme''

* Jalur terpendek dalam graf berarah (AlgoritmaAlgoritme Floyd).

* Implementasi AlgoritmaAlgoritme Floyd-Warshall dalam [[Perl]], yaitu [http://search.cpan.org/~jhi/Graph-0.67/ Graph Module]

* Implementasi AlgoritmaAlgoritme Floyd-Warshall dalam [[Javascript]] di [http://alexle.net/stuff/floyd-algorithm/ Alex Le's Blog]