0-1 BFS ด้วยดีค
หาพาธสั้นที่สุดเมื่อค่าน้ำหนักเป็น 0 หรือ 1
0-1 BFS ด้วยดีค เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
กราฟชนิดพิเศษ
กราฟบางประเภทมีค่าน้ำหนักเส้นเชื่อมเป็นเพียง0 หรือ 1 ในกรณีนี้คุณสามารถใช้เทคนิคที่ง่ายและเร็วกว่าไดก์สตราได้
พบกับ 0-1 BFS
0-1 BFSหาเส้นทางสั้นที่สุดบนกราฟที่มีน้ำหนัก 0 หรือ 1 ได้ในเวลาเชิงเส้น โดยไม่ต้องใช้ฮีปหรือตัวประกอบ log เลย
เครื่องมือ: คิวสองด้าน
เปลี่ยนจากฮีปมาใช้คิวสองด้าน ซึ่งเป็นคิวที่สามารถใส่และนำข้อมูลออกได้จากทั้งด้านหน้าและด้านหลัง
from collections import deque
dq = deque([src])ข้อสังเกตสำคัญ
เส้นเชื่อมที่มีน้ำหนัก0จะคงระยะทางเดิมไว้ ส่วนเส้นเชื่อมที่มีน้ำหนัก 1 จะเพิ่มระยะทางขึ้นหนึ่ง คิวสองด้านจะรักษาลำดับของทั้งสองกลุ่มนี้ไว้
ด้านหน้าสำหรับเส้นเชื่อมศูนย์
ข้ามเส้นเชื่อมที่มีน้ำหนัก 0 ใช่หรือไม่ ให้ใช้ appendleft กับโหนดข้างเคียง เพื่อให้โหนดนั้นถูกประมวลผลถัดไป เพราะไม่มีระยะทางเพิ่ม
dq.appendleft(v)ด้านหลังสำหรับเส้นเชื่อมหนึ่ง
ข้ามเส้นเชื่อมที่มีน้ำหนัก 1 ใช่หรือไม่ ให้ใช้ append กับโหนดข้างเคียงเพื่อใส่ไว้ด้านหลัง เพราะโหนดนั้นอยู่ห่างจากจุดเริ่มต้นออกไปอีกหนึ่งชั้น
dq.append(v)นำข้อมูลออกจากด้านหน้า
ใช้popleftเพื่อนำโหนดปัจจุบันออกมาเสมอ วิธีนี้จะทำให้คิวสองด้านเรียงตามระยะทาง คล้ายกับการทำ BFS แบบแบ่งเป็นชั้น
u = dq.popleft()ปรับปรุงระยะทางด้วยน้ำหนัก
ปรับปรุงระยะทางของเส้นเชื่อมแต่ละเส้น โดยคำนวณระยะทางใหม่เป็น dist[u] บวกกับน้ำหนักเส้นเชื่อม จากนั้นใส่ข้อมูลไว้ด้านหน้าหรือด้านหลังตามน้ำหนักนั้น
nd = dist[u] + w
if nd < dist[v]:
dist[v] = ndเหตุผลที่ลำดับยังคงถูกต้อง
คิวสองด้านจะมีระยะทางที่แตกต่างกันมากที่สุดเพียงสองค่าในเวลาเดียวกัน ค่าคงรูปนี้เองคือเหตุผลที่การใส่ข้อมูลด้านหน้าและด้านหลังทำงานได้
ความเร็วเชิงเส้น
เนื่องจากไม่ต้องใช้ฮีป 0-1 BFS จึงใช้เวลา O(V + E) ซึ่งเร็วกว่าไดก์สตราอย่างเห็นได้ชัดบนกราฟเดียวกัน
ควรเลือกใช้เมื่อใด
ใช้วิธีนี้เมื่อการเคลื่อนที่ไม่มีค่าใช้จ่ายหรือมีค่าใช้จ่ายหนึ่ง เช่น ตารางที่บางก้าวถูกกีดขวางและบางก้าวเปิดให้ผ่านได้
ตรวจสอบสั้น ๆ
คุณปรับปรุงระยะทางของโหนดข้างเคียงผ่านเส้นเชื่อมที่มีน้ำหนัก 0 โหนดนั้นควรไปอยู่ที่ใด
ทบทวน: 0-1 BFS
ใช้คิวสองด้าน โดยใส่เส้นเชื่อมน้ำหนัก 0 ไว้ด้านหน้า และเส้นเชื่อมน้ำหนัก 1 ไว้ด้านหลัง คุณจะได้เส้นทางสั้นที่สุดในเวลา O(V+E) ที่เรียบง่าย ⚡
คำถามที่พบบ่อย
บทเรียน “0-1 BFS ด้วยดีค” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “0-1 BFS ด้วยดีค” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “0-1 BFS ด้วยดีค”
หาพาธสั้นที่สุดเมื่อค่าน้ำหนักเป็น 0 หรือ 1 คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “0-1 BFS ด้วยดีค” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ