# Algoritma Floyd-Warshall

### Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.

| Artikel ini belum atau baru diterjemahkan sebagian dari bahasa Inggris. Bantulah Wikipedia untuk melanjutkannya. Lihat panduan penerjemahan Wikipedia.

Algoritma Floyd-Warshall menghitung jarak terpendek untuk semua pasangan titik pada sebuah graf, dan melakukannya dalam waktu berorde kubik.

## [sunting] 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 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).

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
    }

## [sunting] Aplikasi dan Generalisasi

    --belum diterjemahkan--

## [sunting] Implementasi

- Implementasi Algoritma Floyd-Warshall dalam Perl, yaitu Graph Module
- Implementasi Algoritma Floyd-Warshall dalam Javascript di Alex Le's Blog

## [sunting] Referensi

- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms, first edition, MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
  - 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. Templat:Doi.
- Kleene, S. C. (1956). "Representation of events in nerve nets and finite automata", in C. E. Shannon and J. McCarthy: Automata Studies. Princeton University Press, pp. 3–42.
- Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM 9 (1): 11–12. Templat:Doi.

## [sunting] Pranala luar

- Interactive animation of Floyd-Warshall algorithm

Diperoleh dari "http://id.wikipedia.org../../../a/l/g/Algoritma_Floyd-Warshall_e6a0.html"

Kategori: Artikel yang perlu diterjemahkan dari bahasa Inggris • Matematika diskret

##### Views

- Artikel
- Pembicaraan
- Revisi sekarang

##### Cari

##### Bahasa lain

- Deutsch
- English
- Español
- Français
- עברית
- Italiano
- 日本語
- Polski
- Português
- Српски / Srpski
- 中文