0Pricing
Coding Interview Prep · Pelajaran

Bellman-Ford dan Siklus Negatif

Jalankan n-1 lintasan relaksasi pada semua sisi, deteksi siklus negatif dengan lintasan terakhir, dan jelaskan mengapa Dijkstra gagal pada sisi berbobot negatif

Bellman-Ford dan Siklus Negatif adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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.

Mengapa Bellman-Ford Ada

Bellman-Ford menyelesaikan masalah jalur terpendek dari satu sumber seperti Dijkstra, tetapi juga menangani bobot sisi negatif. Algoritma ini juga mendeteksi siklus negatif—siklus yang total bobotnya negatif sehingga jalur terpendek hingga yang melewatinya tidak dapat ditentukan. Meskipun lebih lambat daripada Dijkstra, Bellman-Ford adalah pilihan yang tepat kapan pun graf mungkin berisi sisi berbobot negatif.

Relaksasi: Operasi Inti

Bellman-Ford dibangun berdasarkan satu operasi: relaksasi. Merelaksasi sisi (u, v, w) berarti: jika dist[u] + w < dist[v], perbarui dist[v] = dist[u] + w. Kita berulang kali merelaksasi semua sisi. Inti pentingnya adalah: setiap jalur terpendek memiliki paling banyak V-1 sisi (dalam graf tanpa siklus negatif). Oleh karena itu, V-1 putaran relaksasi terhadap semua sisi sudah cukup untuk menemukan semua jalur terpendek.

Implementasi Bellman-Ford

Representasikan graf sebagai daftar sisi [(u, v, weight)]. Inisialisasikan dist[source] = 0 dan semua nilai lainnya sebagai inf. Jalankan V-1 putaran dengan merelaksasi semua sisi pada setiap putaran. Setiap pembaruan yang masih terjadi pada putaran ke-V menunjukkan adanya siklus negatif.

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

Mengapa V-1 Putaran Sudah Cukup

Jalur terpendek dalam graf tanpa siklus negatif mengunjungi setiap simpul paling banyak satu kali, sehingga memiliki paling banyak V-1 sisi. Setelah putaran 1, jalur terpendek dengan 1 lompatan sudah optimal. Setelah putaran 2, jalur terpendek dengan 2 lompatan sudah optimal. Setelah V-1 putaran, semua jalur terpendek yang menggunakan paling banyak V-1 lompatan telah ditemukan. Jika putaran V masih memperbarui suatu jarak, graf tersebut memiliki siklus negatif yang dapat dicapai dari sumber.

Mendeteksi Siklus Negatif

Setelah V-1 putaran, jalankan satu putaran tambahan terhadap semua sisi. Jika ada sisi (u, v, w) yang memenuhi dist[u] + w < dist[v], berarti terdapat siklus negatif dan jalur terpendek ke beberapa simpul adalah -infinity. Penerapan di dunia nyata mencakup pendeteksian peluang arbitrase dalam pertukaran mata uang (siklus negatif pada graf berbobot log) dan pendeteksian ketidakkonsistenan dalam sistem kendala.

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

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

Perbandingan Dijkstra dan Bellman-Ford

Dijkstra: O((V+E) log V), memerlukan bobot non-negatif, dan menggunakan pendekatan rakus. Bellman-Ford: O(V × E), menangani bobot negatif, dan mendeteksi siklus negatif. Untuk sebagian besar masalah wawancara dengan bobot non-negatif, Dijkstra lebih disukai. Saat bobot negatif muncul, misalnya ‘temukan jalur terpendek dengan sisi berbobot negatif’ atau ‘deteksi arbitrase’, jawabannya adalah Bellman-Ford. Untuk graf padat, kasus terburuk Bellman-Ford sebesar O(V³) sebanding dengan Floyd-Warshall.

Penerapan: Penerbangan Termurah dengan Bellman-Ford

Penerbangan Termurah dengan K Pemberhentian (LeetCode 787) dapat diselesaikan dengan Bellman-Ford yang dimodifikasi: jalankan tepat k+1 putaran relaksasi, karena k pemberhentian berarti k+1 sisi. Gunakan salinan jarak dari putaran sebelumnya untuk memastikan kita tidak menggunakan lebih banyak lompatan daripada yang diizinkan dalam satu putaran—jika tidak, satu putaran dapat merangkai beberapa lompatan.

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA: Pengoptimalan Berbasis Antrean

Algoritma Jalur Terpendek Lebih Cepat (SPFA) adalah Bellman-Ford yang dioptimalkan dan hanya merelaksasi ulang sisi dari simpul yang jaraknya baru saja diperbarui, menggunakan (using) sebuah antrean. Kasus rata-ratanya adalah O(E), tetapi kasus terburuknya tetap O(V × E). SPFA jarang diperlukan dalam wawancara, tetapi Anda dapat menyebutkannya sebagai pengoptimalan ketika Bellman-Ford terlalu lambat pada graf jarang. Python tidak memiliki SPFA bawaan, tetapi algoritma ini mudah diimplementasikan dengan collections.deque.

Mendeteksi Arbitrase Mata Uang

Penerapan klasik Bellman-Ford: dengan diberikan nilai tukar mata uang, deteksi apakah arbitrase mungkin terjadi, yaitu siklus yang setelah konversi mata uang menghasilkan lebih banyak daripada jumlah awal. Transformasikan nilai tersebut dengan mengambil logaritma negatif dari nilai tukar. Arbitrase = siklus dengan total bobot log negatif = siklus negatif yang dapat dideteksi oleh Bellman-Ford. Dengan demikian, masalah keuangan dunia nyata dapat dipetakan ke algoritma standar.

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

Pengoptimalan Penghentian Dini

Jika tidak ada jarak yang diperbarui dalam satu putaran penuh terhadap semua sisi, putaran berikutnya juga tidak akan memperbarui apa pun—akhiri lebih awal. Pengoptimalan ini mengurangi kompleksitas kasus terbaik menjadi O(E) ketika graf sudah optimal setelah beberapa putaran saja. Tambahkan (add) sebuah penanda updated = False di awal setiap putaran; jika nilainya tetap False setelah putaran selesai, segera hentikan perulangan.

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

Bellman-Ford pada Graf dengan Daftar Ketetanggaan

Jika graf diberikan sebagai daftar ketetanggaan, bukan daftar sisi, ubahlah terlebih dahulu menjadi daftar sisi atau iterasikan semua entri daftar ketetanggaan sebagai sisi. Untuk V=1000 dan E=5000, V-1=999 putaran yang masing-masing memindai 5000 sisi menghasilkan 4.995.000 operasi—jauh di bawah batas waktu. Untuk graf yang sangat padat (E ≈ V²), kasus terburuk O(V³) sama dengan Floyd-Warshall, sehingga pilihannya bergantung pada konteks.

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

Pemeriksaan Singkat

Ujilah pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.

Ringkasan Pelajaran

Dalam pelajaran ini, Anda mempelajari bahwa: Bellman-Ford merelaksasi semua sisi sebanyak V-1 kali untuk menangani sisi berbobot negatif, putaran relaksasi ke-V yang masih menemukan perbaikan menunjukkan adanya siklus negatif, dan algoritma ini memiliki kompleksitas O(V × E), dibandingkan dengan Dijkstra yang memiliki kompleksitas O((V+E) log V). Berikutnya, kita membahas Floyd-Warshall untuk menemukan jalur terpendek antara semua pasangan dalam satu perhitungan O(V³).

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Bellman-Ford dan Siklus Negatif” gratis?

Ya — teks lengkap “Bellman-Ford dan Siklus Negatif” 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 “Bellman-Ford dan Siklus Negatif”?

Jalankan n-1 lintasan relaksasi pada semua sisi, deteksi siklus negatif dengan lintasan terakhir, dan jelaskan mengapa Dijkstra gagal pada sisi berbobot negatif 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 2 dari 4.

Berapa lama pelajaran “Bellman-Ford dan Siklus Negatif” 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