Bellman-Ford dan Kitaran Negatif
Jalankan n-1 lelaran pelonggaran terhadap semua sisi, kesan kitaran negatif dengan lelaran terakhir, dan terangkan sebab Dijkstra gagal pada sisi berbobot negatif.
Bellman-Ford dan Kitaran Negatif ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Mengapa Bellman-Ford Wujud
Bellman-Ford menyelesaikan masalah laluan terpendek dari satu sumber seperti Dijkstra, tetapi ia mengendalikan pemberat sisi negatif. Ia juga mengesan kitaran negatif — kitaran yang jumlah pemberatnya negatif, sehingga mustahil untuk menentukan laluan terpendek terhingga yang melaluinya. Walaupun lebih perlahan daripada Dijkstra, Bellman-Ford ialah pilihan yang tepat apabila graf mungkin mengandungi sisi dengan pemberat negatif.
Relaksasi: Operasi Teras
Bellman-Ford dibina berasaskan satu operasi: relaksasi. Melakukan relaksasi pada sisi (u, v, w) bermaksud: jika dist[u] + w < dist[v], kemas kini dist[v] = dist[u] + w. Kita mengulangi relaksasi pada semua sisi. Wawasan utama ialah: mana-mana laluan terpendek mempunyai paling banyak V-1 sisi (dalam graf tanpa kitaran negatif). Oleh itu, V-1 pusingan relaksasi terhadap semua sisi sudah mencukupi untuk menemukan semua laluan terpendek.
Pelaksanaan Bellman-Ford
Wakili graf sebagai senarai sisi [(u, v, weight)]. Mulakan dengan dist[source] = 0 dan tetapkan semua yang lain kepada inf. Jalankan V-1 pusingan dengan melakukan relaksasi pada semua sisi dalam setiap pusingan. Sebarang kemas kini yang masih berlaku pada pusingan ke-V menunjukkan adanya kitaran 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 Pusingan Sudah Mencukupi
Laluan terpendek dalam graf tanpa kitaran negatif melawati setiap nod paling banyak sekali, jadi laluan itu mempunyai paling banyak V-1 sisi. Selepas pusingan 1, laluan terpendek dengan 1 lompatan adalah optimum. Selepas pusingan 2, laluan terpendek dengan 2 lompatan adalah optimum. Selepas V-1 pusingan, semua laluan terpendek (yang menggunakan paling banyak V-1 lompatan) telah ditemukan. Jika pusingan V masih mengemas kini sesuatu jarak, graf itu mengandungi kitaran negatif yang boleh dicapai dari sumber.
Pengesanan Kitaran Negatif
Selepas V-1 pusingan, jalankan satu pusingan tambahan terhadap semua sisi. Jika mana-mana sisi (u, v, w) memenuhi dist[u] + w < dist[v], maka wujud kitaran negatif dan laluan terpendek ke sesetengah nod ialah -infinity. Aplikasi dunia sebenar termasuk mengesan peluang arbitraj dalam pertukaran mata wang (kitaran negatif dalam graf dengan pemberat log) dan mengesan ketidakselarasan dalam sistem kekangan.
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)) # TrueMembandingkan Dijkstra dengan Bellman-Ford
Dijkstra: O((V+E) log V), memerlukan pemberat tidak negatif, pendekatan tamak. Bellman-Ford: O(V × E), mengendalikan pemberat negatif dan mengesan kitaran negatif. Bagi kebanyakan masalah temu duga dengan pemberat tidak negatif, Dijkstra lebih disukai. Apabila pemberat negatif muncul (contohnya, 'cari laluan terpendek dengan sisi berkos negatif' atau 'kesan arbitraj'), Bellman-Ford ialah jawapannya. Untuk graf padat, kes terburuk Bellman-Ford, iaitu O(V³), setanding dengan Floyd-Warshall.
Aplikasi: Penerbangan Termurah dengan Bellman-Ford
Penerbangan Termurah dalam K Hentian (LeetCode 787) boleh diselesaikan dengan Bellman-Ford yang diubah suai: jalankan tepat k+1 pusingan relaksasi (kerana k hentian bermaksud k+1 sisi). Gunakan salinan jarak daripada pusingan sebelumnya untuk memastikan kita tidak menggunakan lebih banyak lompatan daripada yang dibenarkan dalam satu pusingan — jika tidak, satu pusingan boleh merangkaikan 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)) # 200SPFA: Pengoptimuman Berasaskan Baris Gilir
Algoritma Laluan Terpendek Lebih Pantas (SPFA) ialah Bellman-Ford yang dioptimumkan dan hanya melakukan relaksasi semula terhadap sisi daripada nod yang jaraknya baru sahaja dikemas kini, dengan menggunakan baris gilir. Kes puratanya ialah O(E), tetapi kes terburuknya masih O(V × E). SPFA jarang diperlukan dalam temu duga, tetapi anda boleh menyebutnya sebagai pengoptimuman apabila Bellman-Ford terlalu perlahan pada graf jarang. Python tidak menyediakan SPFA terbina dalam, tetapi algoritma ini mudah dilaksanakan dengan collections.deque.
Pengesanan Arbitraj Mata Wang
Aplikasi klasik Bellman-Ford: berdasarkan kadar pertukaran mata wang, kesan sama ada arbitraj boleh berlaku (iaitu kitaran yang apabila mata wang ditukar, hasilnya melebihi jumlah permulaan). Lakukan transformasi dengan mengambil logaritma negatif bagi kadar pertukaran. Arbitraj = kitaran dengan jumlah pemberat log negatif = kitaran negatif yang dapat dikesan oleh Bellman-Ford. Hal ini memetakan masalah kewangan dunia sebenar kepada algoritma piawai.
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 FalsePengoptimuman Penamatan Awal
Jika tiada jarak dikemas kini dalam satu pusingan penuh merentasi semua sisi, pusingan seterusnya juga tidak akan mengemas kini apa-apa — tamatkan algoritma lebih awal. Pengoptimuman ini mengurangkan kerumitan kes terbaik kepada O(E) apabila graf sudah optimum selepas beberapa pusingan sahaja. Tambahkan bendera updated = False pada permulaan setiap pusingan; jika nilainya kekal False selepas pusingan tersebut, hentikan algoritma serta-merta.
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 distBellman-Ford pada Graf dengan Senarai Ketetanggaan
Apabila graf diberikan sebagai senarai ketetanggaan dan bukannya senarai sisi, tukarkannya kepada senarai sisi terlebih dahulu atau ulangi semua entri senarai ketetanggaan sebagai sisi. Untuk V=1000 dan E=5000, V-1=999 pusingan yang setiap satunya mengimbas 5000 sisi menghasilkan 4,995,000 operasi — masih jauh dalam had masa. Untuk graf yang sangat padat (E ≈ V²), kes terburuk O(V³) sepadan dengan Floyd-Warshall, jadi pilihan 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 distSemakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Imbas Kembali Pelajaran
Dalam pelajaran ini, anda telah mempelajari bahawa: Bellman-Ford melakukan relaksasi pada semua sisi sebanyak V-1 kali untuk mengendalikan sisi dengan pemberat negatif, pusingan relaksasi ke-V yang masih menemukan penambahbaikan menunjukkan kitaran negatif, dan algoritma ini mempunyai kerumitan O(V × E) berbanding O((V+E) log V) bagi Dijkstra. Seterusnya, kita membincangkan Floyd-Warshall untuk laluan terpendek semua pasangan dalam satu pengiraan O(V³).
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Bellman-Ford dan Kitaran Negatif” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Bellman-Ford dan Kitaran Negatif”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Bellman-Ford dan Kitaran Negatif”?
Jalankan n-1 lelaran pelonggaran terhadap semua sisi, kesan kitaran negatif dengan lelaran terakhir, dan terangkan sebab Dijkstra gagal pada sisi berbobot negatif. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Bellman-Ford dan Kitaran Negatif” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Algoritma Dijkstra dengan Baris Keutamaan
- Bellman-Ford dan Kitaran Negatif
- Floyd-Warshall: Laluan Terpendek Semua Pasangan
- Masa Kelewatan Rangkaian dan Pembinaan Semula Laluan