Floyd-Warshall

Dijkstra dan Bellman-Ford hanya menjawab satu pertanyaan: jarak dari satu sumber ke semua node. Namun banyak persoalan nyata membutuhkan jarak antar semua pasangan node — analisis sentralitas graph, perhitungan diameter network, transitive closure, atau query jarak dinamis. Floyd-Warshall menyelesaikan all-pairs shortest path (APSP) dengan elegan: dynamic programming tiga dimensi yang di-optimasi menjadi matriks dua dimensi, dalam waktu O(V³). Pada Chapter ini kita akan membedah recurrencenya, mengimplementasikannya dalam C++ yang ramping (~10 baris inti), dan melihat bagaimana algoritma ini juga mendeteksi siklus berbobot negatif.

Aturan: All-Pairs Shortest Path #

Diberikan graph berarah berbobot (boleh negatif), cari jarak terpendek antara setiap pasangan (i, j). Output: matriks dist[i][j] berisi jarak minimum, atau INF bila tidak terjangkau. Algoritma juga harus mendeteksi bila terdapat siklus berbobot negatif.

Mekanisme: DP over Intermediate Vertex #

Ide brilian Floyd-Warshall: bertanya bertahap, “berapa jarak i → j jika node intermediate yang diperbolehkan hanya {0, 1, ..., k}?” Notasi d[k][i][j] = jarak minimum dari i ke j menggunakan intermediate dari himpunan {0, 1, ..., k-1}.

Recurrence:

d[k][i][j] = min(d[k-1][i][j],          // tidak lewat k
                 d[k-1][i][k] + d[k-1][k][j])  // lewat k

Basis d[0][i][j] = bobot edge langsung i → j, atau INF bila tidak ada, atau 0 bila i == j.

Optimasi ruang: karena d[k] hanya bergantung pada d[k-1], kita bisa pakai matriks 2D dan update in-place. Loop k di luar, i dan j di dalam — urutan ini krusial untuk kebenaran.

Implementasi Floyd-Warshall #

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

const long long INF = LLONG_MAX / 4;

// Floyd-Warshall: all-pairs shortest path
// Mengembalikan (sukses, dist). sukses=false bila ada siklus berbobot negatif.
std::pair<bool, std::vector<std::vector<long long>>>
floyd_warshall(int n, std::vector<std::vector<long long>> w) {
    // w adalah matriks adjacency: w[u][v] = bobot edge u->v, INF bila tidak ada
    // Diagonal = 0
    std::vector<std::vector<long long>> dist = w;
    for (int i = 0; i < n; ++i) dist[i][i] = 0;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (dist[i][k] == INF) continue;
            for (int j = 0; j < n; ++j) {
                if (dist[k][j] == INF) continue;
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // Cek siklus negatif: dist[i][i] < 0 berarti ada siklus berbobot negatif
    for (int i = 0; i < n; ++i) {
        if (dist[i][i] < 0) return {false, {}};
    }
    return {true, dist};
}

int main() {
    // Graph 4 node (directed, weighted, ada 1 edge negatif):
    //   0 -(5)-> 1
    //   0 -(2)-> 3
    //   1 -(3)-> 2
    //   2 -(-1)-> 3
    //   3 -(4)-> 1
    int n = 4;
    std::vector<std::vector<long long>> w(n, std::vector<long long>(n, INF));
    auto add = [&](int u, int v, long long weight) { w[u][v] = weight; };
    add(0, 1, 5); add(0, 3, 2);
    add(1, 2, 3);
    add(2, 3, -1);
    add(3, 1, 4);

    auto [ok, dist] = floyd_warshall(n, w);
    if (!ok) {
        std::cout << "Siklus berbobot negatif terdeteksi!\n";
        return 0;
    }

    std::cout << "Matriks jarak semua pasangan (INF = tidak terjangkau):\n";
    std::cout << "      ";
    for (int j = 0; j < n; ++j) std::cout << j << "    ";
    std::cout << '\n';
    for (int i = 0; i < n; ++i) {
        std::cout << "  " << i << " : ";
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == INF) std::cout << "INF  ";
            else std::cout << dist[i][j] << "    ";
        }
        std::cout << '\n';
    }

    std::cout << "\nTrace:\n";
    std::cout << "  dist[0][1] = 5 (edge langsung 0->1)\n";
    std::cout << "  dist[0][2] = 8 (0->1->2 = 5+3)\n";
    std::cout << "  dist[0][3] = 2 (edge langsung 0->3)\n";
    std::cout << "  dist[1][3] = 2 (1->2->3 = 3+(-1) = 2, lebih murah dari INF)\n";
    std::cout << "  dist[2][1] = 3 (2->3->1 = (-1)+4 = 3, lebih murah dari INF)\n";
    std::cout << "  dist[3][2] = 7 (3->1->2 = 4+3 = 7, lebih murah dari INF)\n";
    return 0;
}

Output yang Dihasilkan:

Matriks jarak semua pasangan (INF = tidak terjangkau):
      0    1    2    3    
  0 : 0    5    8    2    
  1 : INF  0    3    2    
  2 : INF  3    0   -1    
  3 : INF  4    7    0    

Trace:
  dist[0][1] = 5 (edge langsung 0->1)
  dist[0][2] = 8 (0->1->2 = 5+3)
  dist[0][3] = 2 (edge langsung 0->3)
  dist[1][3] = 2 (1->2->3 = 3+(-1) = 2, lebih murah dari INF)
  dist[2][1] = 3 (2->3->1 = (-1)+4 = 3, lebih murah dari INF)
  dist[3][2] = 7 (3->1->2 = 4+3 = 7, lebih murah dari INF)

Bedah Kode Baris-per-Baris #

1. std::vector<std::vector<long long>> w(n, std::vector<long long>(n, INF)): matriks adjacency. w[u][v] = bobot edge, atau INF bila tidak ada edge. Bobot bisa negatif.
2. dist[i][i] = 0: inisialisasi diagonal. Jarak dari node ke dirinya sendiri = 0. Tanpa baris ini, dist[i][i] bisa saja diupdate melalui siklus (yang mungkin saja negatif → deteksi nanti).
3. for (int k = 0; k < n; ++k): loop intermediate node k di luar. Urutan ini wajib — bila k di dalam, algoritma tidak akan menghitung jalur multi-hop dengan benar.
4. if (dist[i][k] == INF) continue;: optimasi praktis. Bila i → k tidak terjangkau, tidak ada gunanya mencoba update i → k → j.
5. if (dist[k][j] == INF) continue;: optimasi serupa untuk k → j.
6. dist[i][j] = dist[i][k] + dist[k][j]: in-place update. Karena dist[i][k] dan dist[k][j] sudah optimal untuk intermediate {0..k-1}, dan kita sedang mengupdate dist[i][j] untuk intermediate {0..k}, update in-place setara dengan d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]).
7. if (dist[i][i] < 0) return {false, {}}: deteksi siklus berbobot negatif. Bila dist[i][i] menjadi negatif, artinya ada siklus dari i ke i dengan total bobot negatif — jarak bisa di--∞.
8. dist[0][3] = 2 bukan 7: path 0 → 3 langsung (bobot 2) lebih pendek dari 0 → 1 → 2 → 3 (5 + 3 + (-1) = 7). Floyd-Warshall menemukan keduanya dan memilih minimum.
9. dist[1][3] = 2: jalur terpendek 1 → 2 → 3 (3 + (-1) = 2), bukan edge langsung (tidak ada). Floyd-Warshall menemukan ini saat k=2 dan k=3.
10. dist[2][1] = 3: jalur 2 → 3 → 1 ((-1) + 4 = 3). Floyd-Warshall menemukan ini saat k=3 karena di iterasi k=3 baru dist[2][3] dan dist[3][1] sudah optimal.

Trace Iterasi (Sketsa) #

Setelah k=n-1, semua pasangan sudah optimal (atau siklus negatif terdeteksi).

Kompleksitas #

Komparasi APSP: Floyd-Warshall vs Dijkstra Beruntun #

Aplikasi Nyata #

• Transitive closure graph: dist[i][j] < INF → i dapat mencapai j. Modifikasi: set boolean reachable.
• Network diameter: maksimum dari dist[i][j] untuk semua pasangan.
• Centrality analysis: hitung betweenness centrality (node yang sering jadi intermediate).
• Routing table: pada network kecil, semua jarak precomputed sekali untuk query cepat.
• Regular expression matching: implementasi Kleene’s algorithm yang analog.

Rekonstruksi Path (Bonus) #

Untuk mendapatkan path aktual i → ... → j (bukan hanya jarak), simpan matriks next[i][j] yang menyimpan node intermediate pertama dari i ke j:

// Saat update:
if (dist[i][k] + dist[k][j] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j];
    next[i][j] = next[i][k];  // atau k, tergantung konvensi
}

// Rekonstruksi:
std::vector<int> path;
for (int cur = i; cur != j; cur = next[cur][j]) path.push_back(cur);
path.push_back(j);

Ringkasan #

• Floyd-Warshall menyelesaikan APSP dengan DP tiga dimensi yang dioptimasi menjadi matriks 2D.
• Recurrence: d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]).
• Loop k di luar, i dan j di dalam — urutan ini wajib.
• Kompleksitas O(V³) waktu, O(V²) ruang.
• Mendukung bobot negatif dan mendeteksi siklus berbobot negatif (dist[i][i] < 0).
• Cocok untuk V ≤ 500 atau graph dense.

Bab berikutnya beralih ke topik baru: Minimum Spanning Tree — definisi, properti, dan ikhtisar algoritma MST klasik.