Dijkstra ด้วยฮีป
หาพาธสั้นที่สุดแบบโลภบนเส้นเชื่อมที่ไม่ติดลบ
Dijkstra ด้วยฮีป เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาเส้นทางสั้นที่สุด
คุณต้องการเส้นทางที่มีค่าใช้จ่ายต่ำที่สุดจากโหนดหนึ่งไปยังโหนดอื่นทุกโหนด ไดก์สตราแก้ปัญหานี้ได้เมื่อค่าน้ำหนักของเส้นเชื่อมทุกเส้นเป็นศูนย์หรือค่าบวก
แนวคิดแบบละโมบ
ไดก์สตราเป็นวิธีแบบละโมบ โดยจะขยายโหนดที่ยังไม่เคยเยี่ยมชมและมีระยะทางที่ทราบค่าน้อยที่สุดเสมอ พร้อมเชื่อว่าระยะทางนั้นเป็นค่าที่แน่นอนแล้ว
เหตุผลที่ใช้ฮีปขั้นต่ำ
หากต้องการหยิบโหนดที่ใกล้ที่สุดอย่างรวดเร็ว คุณต้องใช้ฮีปขั้นต่ำ ฮีปจะคืนค่าระยะทางที่น้อยที่สุดในเวลา log n แทนการสแกนที่ช้า
import heapqเริ่มต้นด้วยระยะทาง
กำหนดระยะทางทุกค่าเป็นอนันต์ จากนั้นกำหนดจุดเริ่มต้นเป็นศูนย์ โหนดที่ยังไปไม่ถึงจะคงค่าอนันต์ไว้ตลอด
dist = [float('inf')] * n
dist[src] = 0ใส่ค่าเริ่มต้นลงในฮีป
ใส่จุดเริ่มต้นเป็นทูเพิลของ (ระยะทาง, โหนด) การวางระยะทางไว้ก่อนทำให้ฮีปจัดเรียงรายการตามค่าใช้จ่ายโดยอัตโนมัติ
pq = [(0, src)]นำโหนดที่ใกล้ที่สุดออก
ในแต่ละรอบ ให้นำค่า (d, u) ที่น้อยที่สุดออก ค่า d คือระยะทางสั้นที่สุดไปยัง u ดังนั้นงานของ u จึงเสร็จสิ้นเมื่อนำออกมาแล้ว
d, u = heapq.heappop(pq)ข้ามรายการเก่า
โหนดหนึ่งอาจอยู่ในฮีปพร้อมระยะทางเก่าที่มากกว่าเดิม ให้ข้ามรายการนั้นเมื่อ d มากกว่าระยะทางที่เก็บไว้
if d > dist[u]:
continueปรับปรุงระยะทางของโหนดข้างเคียง
การปรับปรุงระยะทางหมายถึงการลองทำให้ระยะทางไปยังโหนดข้างเคียงดีขึ้น หากการผ่าน u มีค่าใช้จ่ายน้อยกว่า ให้ปรับปรุงระยะทางแล้วใส่โหนดนั้นลงในฮีป
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))เทคนิคการลบแบบขี้เกียจ
ฮีปของไพธอนไม่สามารถปรับปรุงคีย์ได้ จึงใส่รายการซ้ำแล้วละเว้นรายการเก่า วิธีแบบขี้เกียจนี้ทำให้โค้ดสั้นและรวดเร็ว
เวลาที่ใช้
เมื่อใช้ฮีปแบบไบนารี ไดก์สตราใช้เวลา O((V + E) log V) ซึ่งรองรับกราฟที่มีเส้นเชื่อมหลายแสนเส้นได้อย่างสบาย
ระวังน้ำหนักของเส้นเชื่อม
ไดก์สตราใช้ไม่ได้กับเส้นเชื่อมติดลบ เพราะระยะทางที่นำออกมาอาจยังไม่ใช่ค่าที่แน่นอน สำหรับกรณีนี้ให้ใช้เบลล์แมน–ฟอร์ดแทน
ตรวจสอบสั้น ๆ
คุณนำค่า (d, u) ออกมา แต่ d มากกว่า dist[u] คุณควรทำอย่างไร
ทบทวน: ไดก์สตราด้วยฮีป
คุณเริ่มต้นระยะทาง ใส่ค่า (dist, node) ลงในฮีป นำค่าที่ใกล้ที่สุดออก ข้ามรายการเก่า และปรับปรุงระยะทางของโหนดข้างเคียง นั่นคือไดก์สตราในเวลา O((V+E) log V) 🚀
คำถามที่พบบ่อย
บทเรียน “Dijkstra ด้วยฮีป” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “Dijkstra ด้วยฮีป” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “Dijkstra ด้วยฮีป”
หาพาธสั้นที่สุดแบบโลภบนเส้นเชื่อมที่ไม่ติดลบ คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “Dijkstra ด้วยฮีป” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ