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

Bellman-Ford และเส้นเชื่อมติดลบ

จัดการค่าติดลบและตรวจจับวัฏจักร

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

เมื่อไดก์สตราใช้ไม่ได้

ไดก์สตราเชื่อว่าระยะทางที่นำออกมาเป็นค่าที่แน่นอนแล้ว แต่เส้นเชื่อมติดลบอาจทำให้ภายหลังพบเส้นทางที่มีค่าใช้จ่ายต่ำกว่า ดังนั้นวิธีนี้จึงใช้ไม่ได้

พบกับเบลล์แมน–ฟอร์ด

เบลล์แมน–ฟอร์ดรองรับน้ำหนักเส้นเชื่อมติดลบ แม้จะช้ากว่าไดก์สตรา แต่ก็เชื่อถือได้ในกรณีที่ตรรกะแบบละโมบใช้ไม่ได้

การดำเนินการหลัก

วิธีนี้จะปรับปรุงระยะทางของเส้นเชื่อมทุกเส้นซ้ำ ๆ หาก dist[u] บวกกับน้ำหนักเส้นเชื่อมน้อยกว่า dist[v] ให้ปรับ dist[v] เป็นค่าที่น้อยกว่านั้น

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

ต้องทำกี่รอบ

เส้นทางสั้นที่สุดใช้เส้นเชื่อมไม่เกิน V ลบ 1 เส้น ดังนั้นการปรับปรุงระยะทาง V-1 รอบ โดยพิจารณาเส้นเชื่อมทุกเส้นก็เพียงพอที่จะทำให้ระยะทางทั้งหมดแน่นอน

for _ in range(n - 1):
    relax_all_edges()

เริ่มต้นระยะทาง

เริ่มต้นด้วยระยะทางทุกค่าเป็นอนันต์ ยกเว้นจุดเริ่มต้นที่เป็นศูนย์ เช่นเดียวกับที่ทำในไดก์สตรา

dist = [float('inf')] * n
dist[src] = 0

การผ่านครบหนึ่งรอบ

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

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

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

หลังผ่านไป k รอบ เส้นทางสั้นที่สุดที่ใช้เส้นเชื่อม k เส้นจะถูกต้องทั้งหมด เมื่อครบ V-1 รอบ เส้นทางสั้นที่สุดแบบไม่วนซ้ำทุกเส้นก็เสร็จสมบูรณ์

รอบพิเศษ

ให้ทำอีกหนึ่งรอบ หากระยะทางใด ๆ ยังคงลดลง แสดงว่ายังมีทางที่ทำให้ค่าใช้จ่ายลดลงได้เรื่อย ๆ ซึ่งเป็นสัญญาณว่ามีวงจรติดลบ

ตรวจหาวงจรติดลบ

วงจรติดลบหมายความว่าไม่มีเส้นทางสั้นที่สุดที่มีค่าจำกัด เพราะคุณสามารถวนซ้ำไปเรื่อย ๆ เพื่อลดค่าใช้จ่ายลงได้ไม่สิ้นสุด

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

เวลาที่ใช้

คุณปรับปรุงระยะทางของเส้นเชื่อม E เส้นเป็นจำนวน V รอบ ดังนั้นเบลล์แมน–ฟอร์ดจึงใช้เวลา O(V * E) ซึ่งเหมาะกับกราฟขนาดเล็กหรือขนาดกลาง

ไดก์สตราหรือเบลล์แมน–ฟอร์ด

เลือกไดก์สตราเมื่อน้ำหนักไม่ติดลบและต้องการความเร็ว เลือกเบลล์แมน–ฟอร์ดเมื่อมีค่าติดลบหรือต้องตรวจจับวงจรที่ไม่ถูกต้อง

ตรวจสอบสั้น ๆ

หลังจากผ่าน V-1 รอบแล้ว ในรอบถัดไประยะทางหนึ่งยังลดลง สิ่งนี้หมายความว่าอย่างไร

ทบทวน: เบลล์แมน–ฟอร์ด

ปรับปรุงระยะทางของเส้นเชื่อมทั้งหมดเป็นเวลา V-1 รอบ แล้วทำอีกหนึ่งรอบเพื่อตรวจจับวงจรติดลบ วิธีนี้ใช้เวลา O(V*E) แต่ทำงานได้ในกรณีที่ไดก์สตราใช้ไม่ได้ ✅

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

บทเรียน “Bellman-Ford และเส้นเชื่อมติดลบ” ฟรีหรือไม่

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

คุณจะเรียนรู้อะไรในบทเรียน “Bellman-Ford และเส้นเชื่อมติดลบ”

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

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

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

บทเรียน “Bellman-Ford และเส้นเชื่อมติดลบ” ใช้เวลานานแค่ไหน

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

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

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

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

  1. Dijkstra ด้วยฮีป
  2. 0-1 BFS ด้วยดีค
  3. Bellman-Ford และเส้นเชื่อมติดลบ
  4. Floyd-Warshall สำหรับทุกคู่
← กลับไปที่ Coding Interview Prep