0Pricing
Coding Interview Prep · บทเรียน

Bellman-Ford และวงจรน้ำหนักลบ

ผ่อนคลายเส้นเชื่อมทั้งหมดจำนวน n-1 รอบ ตรวจจับวงจรน้ำหนักลบด้วยรอบสุดท้าย และอธิบายว่าเหตุใด Dijkstra จึงใช้กับเส้นเชื่อมน้ำหนักลบไม่ได้

Bellman-Ford และวงจรน้ำหนักลบ เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

เหตุผลที่มีเบลล์แมน–ฟอร์ด

เบลล์แมน–ฟอร์ด แก้ปัญหาเส้นทางสั้นที่สุดจากต้นทางเดียวเช่นเดียวกับดิกซ์ตรา แต่รองรับน้ำหนักของเส้นเชื่อมที่ติดลบ และยังตรวจจับวงจรติดลบได้ด้วย วงจรเหล่านี้มีน้ำหนักรวมติดลบ ทำให้ไม่สามารถกำหนดเส้นทางสั้นที่สุดที่มีค่าจำกัดผ่านวงจรดังกล่าวได้ แม้จะช้ากว่าดิกซ์ตรา แต่เบลล์แมน–ฟอร์ดเป็นตัวเลือกที่ถูกต้องเมื่อกราฟอาจมีเส้นเชื่อมที่มีน้ำหนักติดลบ

การผ่อนคลาย: การดำเนินการหลัก

เบลล์แมน–ฟอร์ดสร้างขึ้นจากการดำเนินการเดียวที่เรียกว่าการผ่อนคลาย การผ่อนคลายเส้นเชื่อม (u, v, w) หมายถึง หาก dist[u] + w < dist[v] ให้ปรับปรุง dist[v] = dist[u] + w เราจะผ่อนคลายเส้นเชื่อมทั้งหมดซ้ำไปเรื่อย ๆ แนวคิดสำคัญคือ เส้นทางสั้นที่สุดทุกเส้นมีเส้นเชื่อมไม่เกิน V-1 เส้น ในกราฟที่ไม่มีวงจรติดลบ ดังนั้นการผ่อนคลายเส้นเชื่อมทั้งหมด V-1 รอบก็เพียงพอที่จะหาเส้นทางสั้นที่สุดทั้งหมด

การใช้งานเบลล์แมน–ฟอร์ด

แทนกราฟด้วยรายการเส้นเชื่อม [(u, v, weight)] กำหนดค่าเริ่มต้นให้ dist[source] = 0 และกำหนดค่าอื่นทั้งหมดเป็น inf จากนั้นทำ V-1 รอบ โดยผ่อนคลายเส้นเชื่อมทั้งหมดในแต่ละรอบ หากยังมีการปรับปรุงเกิดขึ้นในรอบที่ V แสดงว่ามีวงจรติดลบ

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]

เหตุใด V-1 รอบจึงเพียงพอ

เส้นทางสั้นที่สุดในกราฟที่ไม่มีวงจรติดลบจะแวะผ่านแต่ละโหนดได้ไม่เกินหนึ่งครั้ง จึงมีเส้นเชื่อมไม่เกิน V-1 เส้น หลังรอบที่ 1 เส้นทางสั้นที่สุดที่ใช้เส้นเชื่อม 1 เส้นจะได้ค่าที่เหมาะสม หลังรอบที่ 2 เส้นทางสั้นที่สุดที่ใช้เส้นเชื่อม 2 เส้นจะได้ค่าที่เหมาะสม และหลังรอบที่ V-1 จะพบเส้นทางสั้นที่สุดทั้งหมด ซึ่งใช้เส้นเชื่อมไม่เกิน V-1 เส้น หากรอบที่ V ยังปรับปรุงระยะทางได้ แสดงว่ากราฟมีวงจรติดลบที่สามารถเข้าถึงได้จากต้นทาง

การตรวจจับวงจรติดลบ

หลังจากทำ V-1 รอบแล้ว ให้ทำอีกรอบหนึ่งกับเส้นเชื่อมทั้งหมด หากมีเส้นเชื่อมใด (u, v, w) ที่เป็นไปตามเงื่อนไข dist[u] + w < dist[v] แสดงว่ามีวงจรติดลบอยู่ และเส้นทางสั้นที่สุดไปยังบางโหนดมีค่าเป็นลบอนันต์ การประยุกต์ใช้ในโลกจริงรวมถึงการตรวจจับโอกาสทำกำไรจากส่วนต่างอัตราแลกเปลี่ยน (วงจรติดลบในกราฟที่มีน้ำหนักเป็น log) และการตรวจจับความไม่สอดคล้องกันในระบบข้อจำกัด

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

การเปรียบเทียบดิกซ์ตรากับเบลล์แมน–ฟอร์ด

ดิกซ์ตรา: O((V+E) log V) ต้องใช้น้ำหนักที่ไม่ติดลบ และใช้แนวทางแบบละโมบ เบลล์แมน–ฟอร์ด: O(V × E) รองรับน้ำหนักติดลบและตรวจจับวงจรติดลบได้ สำหรับโจทย์สัมภาษณ์ส่วนใหญ่ที่น้ำหนักไม่ติดลบ มักเลือกใช้ดิกซ์ตรา เมื่อมีน้ำหนักติดลบ เช่น “หาเส้นทางสั้นที่สุดที่มีเส้นเชื่อมต้นทุนติดลบ” หรือ “ตรวจจับการทำกำไรจากส่วนต่าง” คำตอบคือเบลล์แมน–ฟอร์ด สำหรับกราฟแบบหนาแน่น กรณีเลวร้ายที่สุด O(V³) ของเบลล์แมน–ฟอร์ดมีความใกล้เคียงกับฟลอยด์–วอร์แชลล์

การประยุกต์ใช้: เที่ยวบินราคาถูกที่สุดด้วยเบลล์แมน–ฟอร์ด

โจทย์เที่ยวบินราคาถูกที่สุดภายในการหยุดพักไม่เกิน K ครั้ง (LeetCode 787) แก้ได้ด้วยเบลล์แมน–ฟอร์ดที่ปรับแก้ โดยทำการผ่อนคลาย exactamente k+1 รอบ เนื่องจากการหยุดพัก k ครั้งหมายถึงเส้นเชื่อม k+1 เส้น ให้ใช้สำเนาระยะทางจากรอบก่อนหน้า เพื่อให้แน่ใจว่าเราไม่ใช้เส้นเชื่อมเกินจำนวนที่อนุญาตในรอบเดียว มิฉะนั้นรอบเดียวอาจต่อเส้นเชื่อมหลายเส้นเข้าด้วยกันได้

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: การปรับปรุงแบบใช้คิว

อัลกอริทึมหาเส้นทางสั้นที่สุดที่เร็วขึ้น (SPFA) คือเบลล์แมน–ฟอร์ดที่ปรับปรุงให้ทำการผ่อนคลายเส้นเชื่อมเฉพาะจากโหนดที่เพิ่งมีการปรับปรุงระยะทาง โดยใช้คิว กรณีโดยเฉลี่ยมีความซับซ้อน O(E) แต่กรณีเลวร้ายที่สุดยังคงเป็น O(V × E) โดยทั่วไปแทบไม่จำเป็นต้องใช้ SPFA ในการสัมภาษณ์ แต่สามารถกล่าวถึงเป็นการปรับปรุงเมื่อเบลล์แมน–ฟอร์ดช้าเกินไปบนกราฟแบบเบาบาง ไพธอนไม่มี SPFA ในตัว แต่สามารถใช้งานได้ไม่ยากด้วย collections.deque

การตรวจจับการทำกำไรจากส่วนต่างสกุลเงิน

การประยุกต์ใช้เบลล์แมน–ฟอร์ดที่เป็นคลาสสิกคือ เมื่อกำหนดอัตราแลกเปลี่ยนสกุลเงิน ให้ตรวจสอบว่าสามารถทำกำไรจากส่วนต่างได้หรือไม่ ซึ่งหมายถึงมีวงจรที่เมื่อแปลงสกุลเงินแล้วจะได้รับเงินมากกว่าจำนวนเริ่มต้น ให้แปลงปัญหาด้วยการใช้ลอการิทึมติดลบของอัตราแลกเปลี่ยน การทำกำไรจากส่วนต่าง = วงจรที่มีน้ำหนัก log รวมติดลบ = วงจรติดลบที่เบลล์แมน–ฟอร์ดตรวจจับได้ วิธีนี้เชื่อมโยงปัญหาทางการเงินในโลกจริงเข้ากับอัลกอริทึมมาตรฐาน

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

การปรับปรุงด้วยการยุติก่อนกำหนด

หากไม่มีระยะทางใดได้รับการปรับปรุงตลอดการตรวจสอบเส้นเชื่อมทั้งหมดหนึ่งรอบ รอบถัดไปก็จะไม่ปรับปรุงอะไรเช่นกัน ดังนั้นให้ยุติการทำงานก่อนกำหนด การปรับปรุงนี้ลดความซับซ้อนในกรณีดีที่สุดเหลือ O(E) เมื่อกราฟอยู่ในสภาพเหมาะสมแล้วหลังผ่านไปเพียงไม่กี่รอบ ให้เพิ่มแฟล็ก updated = False ที่จุดเริ่มต้นของแต่ละรอบ หากยังเป็น False หลังจบรอบ ให้หยุดทันที

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

เบลล์แมน–ฟอร์ดบนกราฟที่มีรายการเพื่อนบ้าน

เมื่อกราฟได้รับมาในรูปแบบรายการเพื่อนบ้านแทนรายการเส้นเชื่อม ให้แปลงเป็นรายการเส้นเชื่อมก่อน หรือวนผ่านรายการเพื่อนบ้านทั้งหมดโดยถือว่าแต่ละรายการเป็นเส้นเชื่อม สำหรับ V=1000 และ E=5000 การทำ V-1=999 รอบ โดยตรวจสอบเส้นเชื่อม 5000 เส้นในแต่ละรอบ จะมีการดำเนินการ 4,995,000 ครั้ง ซึ่งยังอยู่ภายในข้อจำกัดด้านเวลา สำหรับกราฟที่หนาแน่นมาก (E ≈ V²) กรณีเลวร้ายที่สุด O(V³) จะเท่ากับฟลอยด์–วอร์แชลล์ ทำให้การเลือกขึ้นอยู่กับบริบท

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

แบบทดสอบสั้น ๆ

ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้

ทบทวนบทเรียน

ในบทเรียนนี้ได้เรียนรู้ว่า: เบลล์แมน–ฟอร์ดผ่อนคลายเส้นเชื่อมทั้งหมด V-1 ครั้งเพื่อรองรับเส้นเชื่อมที่มีน้ำหนักติดลบ หากรอบการผ่อนคลายครั้งที่ V ยังพบการปรับปรุง แสดงว่ามีวงจรติดลบ และ อัลกอริทึมมีความซับซ้อน O(V × E) เมื่อเทียบกับดิกซ์ตราที่มีความซับซ้อน O((V+E) log V) บทถัดไปจะกล่าวถึงฟลอยด์–วอร์แชลล์สำหรับหาเส้นทางสั้นที่สุดระหว่างทุกคู่โหนดด้วยการคำนวณ O(V³) เพียงครั้งเดียว

คำถามที่พบบ่อย

บทเรียน “Bellman-Ford และวงจรน้ำหนักลบ” ฟรีหรือไม่

ใช่ — ข้อความเต็มของ “Bellman-Ford และวงจรน้ำหนักลบ” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน

คุณจะเรียนรู้อะไรในบทเรียน “Bellman-Ford และวงจรน้ำหนักลบ”

ผ่อนคลายเส้นเชื่อมทั้งหมดจำนวน n-1 รอบ ตรวจจับวงจรน้ำหนักลบด้วยรอบสุดท้าย และอธิบายว่าเหตุใด Dijkstra จึงใช้กับเส้นเชื่อมน้ำหนักลบไม่ได้ คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน

คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่

ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน

บทเรียน “Bellman-Ford และวงจรน้ำหนักลบ” ใช้เวลานานแค่ไหน

บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย

ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม

ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ

บทเรียนทั้งหมดในหลักสูตรนี้

  1. อัลกอริทึมของ Dijkstra กับคิวลำดับความสำคัญ
  2. Bellman-Ford และวงจรน้ำหนักลบ
  3. Floyd-Warshall: เส้นทางสั้นที่สุดระหว่างทุกคู่
  4. เวลาหน่วงของเครือข่ายและการสร้างเส้นทางกลับคืน
← กลับไปที่ Coding Interview Prep