0Pricing
Coding Interview Prep · Pelajaran

Floyd-Warshall: Jalur Terpendek Semua Pasangan

Isi matriks jarak semua pasangan menggunakan algoritma Floyd-Warshall dengan tiga perulangan bersarang, lalu terapkan untuk menemukan jumlah lompatan terkecil antara semua pasangan simpul

Floyd-Warshall: Jalur Terpendek Semua Pasangan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Jalur Terpendek antara Semua Pasangan

Floyd-Warshall menghitung jalur terpendek antara setiap pasangan simpul dalam graf berbobot, termasuk graf dengan sisi berbobot negatif, tetapi bukan graf dengan siklus negatif. Menjalankan Dijkstra dari setiap sumber memerlukan waktu O(V × (V+E) log V); Floyd-Warshall berjalan dalam O(V³), terlepas dari kepadatan sisi. Untuk graf padat dengan V ≤ 500, Floyd-Warshall sering kali lebih sederhana dan kecepatannya sebanding.

Gagasan Inti: Simpul Perantara

Inti Floyd-Warshall adalah: dp[i][j][k] = jalur terpendek dari i ke j yang hanya menggunakan (using) simpul {0, 1, ..., k} sebagai perantara. Jalur terpendek tersebut menggunakan simpul k sebagai perantara, atau tidak menggunakannya. Jika menggunakannya: dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1]. Jika tidak: dp[i][j][k] = dp[i][j][k-1]. Karena dimensi ketiga hanya bergerak maju, dimensi tersebut dapat dihilangkan—kita memperbarui nilainya langsung di tempat.

Inisialisasi Matriks Jarak

Mulailah dengan matriks V×V: dist[i][i] = 0 (jarak ke diri sendiri adalah nol), dist[i][j] = weight untuk sisi langsung, dan dist[i][j] = inf untuk pasangan tanpa sisi. Kemudian iterasikan semua simpul perantara k dan perbarui pasangan (i, j). Perulangan luar untuk k harus dijalankan terlebih dahulu agar jalur melalui himpunan simpul perantara yang diizinkan dapat dibangun secara bertahap dan benar.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

Implementasi Lengkap dengan Contoh

Mari kita telusuri Floyd-Warshall pada graf dengan 4 simpul. Setelah setiap simpul perantara k diproses, matriks tersebut terisi dengan jalur-jalur yang lebih pendek melalui simpul k. Algoritma ini secara alami menangani banyak lompatan dengan membangun jalur terpendek secara bertahap.

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

Mendeteksi Siklus Negatif

Setelah menjalankan Floyd-Warshall, periksa diagonal utama: jika ada dist[i][i] < 0, berarti terdapat siklus negatif yang melewati simpul i. Hal ini terjadi karena siklus negatif memungkinkan kita mencapai i dari i dengan biaya negatif. Jika tidak ada siklus negatif, semua entri diagonal tetap bernilai 0.

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

Rekonstruksi Jalur

Untuk merekonstruksi jalur sebenarnya dari i ke j, pertahankan matriks next[i][j]: pada awalnya, next[i][j] = j untuk sisi langsung. Saat memperbarui melalui simpul perantara k, tetapkan next[i][j] = next[i][k]. Untuk mendapatkan kembali jalur tersebut, mulai dari i dan ikuti penunjuk next sampai mencapai j. Cara ini menambahkan penggunaan ruang O(V²) dan waktu O(V) untuk setiap rekonstruksi jalur.

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

Penutupan Transitif

Variasi yang lebih sederhana, Penutupan Transitif, menjawab pertanyaan ‘apakah simpul j dapat dicapai dari simpul i?’ untuk semua pasangan. Ganti jarak dengan nilai benar atau salah: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). Ini adalah Floyd-Warshall dengan OR boolean, bukan penjumlahan dan operasi minimum. Inisialisasikan reach[i][i] = True dan reach[i][j] = True untuk sisi langsung.

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

Kompleksitas dan Kapan Menggunakannya

Floyd-Warshall: O(V³) waktu, O(V²) ruang. Untuk graf padat (E ≈ V²) dengan V ≤ 300, algoritma ini lebih cepat daripada menjalankan Dijkstra sebanyak V kali, yang juga memiliki kompleksitas O(V³) dalam kasus tersebut. Untuk graf jarang dengan V = 1000 dan E = 3000, V kali Dijkstra memerlukan O(V×E×log V) ≈ 33M, sedangkan Floyd-Warshall memerlukan O(V³) = 10⁹—Dijkstra lebih unggul. Pahamilah kapan masing-masing algoritma tepat digunakan.

Jumlah Minimum Lompatan antara Semua Pasangan

Tetapkan semua bobot sisi menjadi 1 (atau gunakan matriks ketetanggaan boolean dengan Floyd-Warshall menggunakan penjumlahan, bukan nilai minimum): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Ini menghitung jumlah minimum lompatan antara semua pasangan—hasil BFS untuk semua pasangan, tetapi dihitung dengan satu lintasan Floyd-Warshall O(V³).

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

Konteks Wawancara: Saat Pewawancara Menanyakan Floyd-Warshall

Floyd-Warshall muncul dalam wawancara pada pertanyaan yang melibatkan: (1) jarak antara semua pasangan pada graf kecil, (2) pencarian apakah terdapat siklus dengan bobot total negatif, (3) penghitungan jalur terpendek dalam masalah propagasi kendala, dan (4) masalah yang secara eksplisit meminta solusi O(V³) dengan V ≤ 200. Selalu sebutkan struktur tiga perulangan dan persyaratan bahwa tidak boleh ada siklus negatif agar hasilnya benar.

Graf Tak Berarah dengan Floyd-Warshall

Untuk graf tak berarah, tambahkan kedua arah untuk setiap sisi: dist[u][v] = dist[v][u] = weight. Algoritme lainnya tetap sama. Matriks yang dihasilkan bersifat simetris: dist[i][j] == dist[j][i] untuk semua pasangan. Saat melakukan inisialisasi, berhati-hatilah agar tidak secara tidak sengaja menetapkan sisi berarah—sisi tak berarah harus ditambahkan dalam kedua arah ke matriks awal sebelum menjalankan tiga perulangan.

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

Uji Cepat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari: Floyd-Warshall menghitung jalur terpendek untuk semua pasangan dengan tiga perulangan bersarang dan relasi dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]), siklus negatif dapat dideteksi dengan memeriksa apakah ada dist[i][i] < 0 setelah penghitungan selesai, dan algoritme ini berjalan dalam waktu O(V³) serta menggunakan ruang O(V²). Selanjutnya, kita meninjau kembali penerapan jalur terpendek dengan Waktu Tunda Jaringan dan teknik rekonstruksi jalur.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Floyd-Warshall: Jalur Terpendek Semua Pasangan” gratis?

Ya — teks lengkap “Floyd-Warshall: Jalur Terpendek Semua Pasangan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Floyd-Warshall: Jalur Terpendek Semua Pasangan”?

Isi matriks jarak semua pasangan menggunakan algoritma Floyd-Warshall dengan tiga perulangan bersarang, lalu terapkan untuk menemukan jumlah lompatan terkecil antara semua pasangan simpul Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.

Berapa lama pelajaran “Floyd-Warshall: Jalur Terpendek Semua Pasangan” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Algoritma Dijkstra dengan Antrean Prioritas
  2. Bellman-Ford dan Siklus Negatif
  3. Floyd-Warshall: Jalur Terpendek Semua Pasangan
  4. Waktu Tunda Jaringan dan Rekonstruksi Jalur
← Kembali ke Coding Interview Prep