เมื่อรู้จุดเริ่มและจุดหมาย การค้นหาเส้นทางจากทั้งสองด้านฟังดูเหมือนทางลัด: เริ่มจากต้นทาง เดินไปข้างหน้า เริ่มจากปลายทาง เดินย้อนกลับ แล้วหยุดเมื่อเส้นทางทั้งคู่มาพบกัน แต่คำว่า “พบกัน” บอกเพียงว่ามีเส้นทางเชื่อมต่อกันได้ ยังไม่ได้พิสูจน์ว่าเส้นทางที่พบมีต้นทุนต่ำที่สุด
คำตอบสั้น ๆ: Bidirectional Dijkstra ค้นจากต้นทางและจากปลายทางบนกราฟย้อนกลับ เก็บเส้นทางสมบูรณ์ที่ดีที่สุดซึ่งพบไว้เป็น μ แล้วหยุดเมื่อผลรวมของระยะทางต่ำสุดที่ยังค้างอยู่ในคิวทั้งสองด้านไม่น้อยกว่า μ สำหรับกราฟมีทิศทาง การค้นย้อนกลับต้องเดินตามขอบขาเข้าของกราฟเดิมและใช้ค่าน้ำหนักเดิม การหยุดทันทีที่พบโหนดร่วมครั้งแรกอาจคืนเส้นทางผิด
บทความนี้แยกให้เห็นความต่างระหว่าง “เจอเส้นทาง” กับ “ยืนยันว่าเป็นเส้นทางสั้นที่สุด” ผ่านตัวอย่างขนาดเล็ก อธิบายข้อมูลที่อัลกอริทึมต้องเก็บ วิธีตรวจเส้นทางคืน และจุดที่การค้นสองด้านอาจไม่ช่วยลดงาน ทั้งหมดนี้เป็นการค้นเส้นทางบนกราฟจำกัดที่กำหนดไว้แล้ว ไม่ใช่หลักฐานว่าระบบวางแผนหรือโมเดลภาษาเข้าใจการกระทำในโลกจริง
ทำไมการพบกันครั้งแรกยังไม่พอ
พิจารณากราฟถ่วงน้ำหนักมีทิศทางที่มีเส้นทางสองสายจาก s ไป t ดังนี้
s --1--> a --9--> t
\
4--> b --4--> tเส้นทางผ่าน a มีต้นทุนรวม 10 ส่วนเส้นทางผ่าน b มีต้นทุนรวม 8 ดังนั้นคำตอบที่ถูกคือ s → b → t ถ้าค้นจาก s และ t แล้วอัลกอริทึมพบโหนด a ร่วมกันก่อน ก็มีหลักฐานเพียงว่าเส้นทาง s → a → t ใช้ได้และมีต้นทุน 10 ยังไม่มีหลักฐานว่าเส้นทางอื่นที่ยังไม่สำรวจจะไม่ถูกกว่า
ความผิดพลาดมักเกิดเมื่อโปรแกรมตรวจการพบกันทันทีระหว่างสร้างโหนดหรือระหว่างผ่อนคลายขอบ แล้วคืนคำตอบทันที ขั้นตอนนั้นอาจเกิดก่อนที่อัลกอริทึมจะตรวจขาออกทั้งหมดของโหนดปัจจุบันด้วยซ้ำ คำว่า “แตะ” หรือ “พบร่วม” จึงไม่ควรเป็นเงื่อนไขหยุดของ weighted search
SIMULATION: เริ่มต้นคิวหน้า s และคิวย้อน t ด้วยระยะ 0 ขยาย s แล้วค้นพบ a ที่ระยะ 1 และ b ที่ระยะ 4 ระหว่างขยาย t ย้อนกลับ เมื่อประมวลผลขอบที่มาจาก a ก่อน จะพบผู้สมัครเส้นทางต้นทุน 1 + 9 = 10 ชั่วคราว; เมื่อประมวลผลขอบจาก b ในการขยายเดียวกัน μ ลดเป็น 8 เมื่อขยาย t เสร็จ α = 1 และ β = 4 จึงรวม 5 < 8 ยังหยุดไม่ได้ ต่อมาเมื่อขยาย a ทางหน้า ผู้สมัคร 10 ไม่เปลี่ยน μ และค่าต่ำสุดกลายเป็น 4 กับ 4 ดังนั้น α + β = 8 = μ จึงหยุดได้
FACT: การชนกันครั้งแรกเป็นเพียง upper bound หรือขอบเขตบนของคำตอบ เพราะเป็นเส้นทางสมบูรณ์ที่มีอยู่จริง ส่วนผลรวมค่าต่ำสุดจากคิวเป็น lower bound หรือขอบเขตล่างของเส้นทางที่อาจยังไม่พบ เมื่อ lower bound ไม่น้อยกว่า upper bound ที่ดีที่สุด ทั้งสองขอบเขตยืนยันว่าคำตอบเท่ากัน
แบบจำลองกราฟและการค้นย้อนกลับ
ให้กราฟเป็น G = (V, E) โดย V คือชุดโหนด และ E คือชุดขอบที่มีทิศทางพร้อมต้นทุน c(u,v) โจทย์รับต้นทาง s และเป้าหมาย t แล้วหาเส้นทางที่ผลรวมต้นทุนต่ำที่สุด สมมติฐานหลักของ Dijkstra คือขอบทุกเส้นมีต้นทุนไม่ติดลบ การมีขอบศูนย์ทำได้ แต่ขอบติดลบทำให้การรับรองระยะทางเมื่อโหนดถูกนำออกจากคิวใช้ไม่ได้
การค้นไปข้างหน้าเริ่มที่ s และติดตามขอบ u → v ในกราฟเดิม ส่วนการค้นย้อนเริ่มที่ t และติดตามขอบที่เข้าสู่โหนดปัจจุบัน ตัวอย่างเช่น ถ้ามีขอบเดิม u → v ที่ต้นทุน 7 การค้นย้อนที่ v จะไปยัง u ด้วยต้นทุน 7 ไม่ได้สร้างขอบต้นทุน 7 จาก v ไป u ในโลกเดิม แต่กำลังสำรวจว่าจาก u มีทางไป v เพื่อประกอบเส้นทางสู่ t อย่างไร
ดังนั้นระบบควรเก็บดัชนีขอบขาออกและขอบขาเข้า หรือมีโครงสร้างกราฟย้อนกลับที่ระบุที่มาของขอบเดิมชัดเจน หากมีเพียงรายการการกระทำจากสถานะหนึ่งไปอีกสถานะหนึ่ง การย้อนค้นต้องสร้าง predecessor ที่ถูกต้อง ไม่ควรเดาว่าการกระทำทุกชนิดย้อนกลับได้ เช่น “เปิดประตู” ไม่ได้แปลว่ามีการกระทำ “ปิดประตู” ที่คืนสู่สถานะเดิมเสมอไป ความถูกต้องของการค้นสองด้านขึ้นกับความถูกต้องของกราฟที่ป้อนเข้ามา
ข้อมูลเข้า ผลลัพธ์ และขอบเขตหน่วยความจำ
สัญญาข้อมูลขั้นต่ำอาจกำหนดเป็น {vertices, edges: {from, to, cost, id}, s, t} โดย id ช่วยแยกขอบซ้ำ ผลลัพธ์คือ {path, cost, status} ซึ่ง status ระบุเส้นทางที่พบหรือไม่มีเส้นทาง อินพุตต้องเป็นกราฟคงที่ระหว่างการค้นและมีต้นทุนไม่ติดลบ ตัวดัชนีขาเข้าเพิ่มการเก็บข้อมูลตามจำนวนขอบ และอัลกอริทึมต้องเก็บระยะ ตัวชี้ คิว และสถานะสองชุดตามจำนวนโหนด การเลือกใช้งานจึงควรคำนึงถึงหน่วยความจำของกราฟกับดัชนี ไม่ใช่เฉพาะเวลาค้น
โครงสร้างข้อมูลที่ทำให้ตรวจสอบได้
อัลกอริทึมต้องเก็บสถานะสองชุดที่แยกจากกันอย่างชัดเจน ฝั่งหน้าเก็บ distF[v] ซึ่งเป็นระยะทางที่ดีที่สุดที่รู้จาก s ไป v พร้อม parentF[v] สำหรับย้อนสร้างเส้นทาง ฝั่งย้อนเก็บ distB[v] ซึ่งเป็นระยะทางที่ดีที่สุดที่รู้จาก v ไป t และ nextB[v] ซึ่งชี้โหนดถัดไปในเส้นทางเดิมไปยัง t ทั้งสองด้านมีคิวลำดับความสำคัญและชุดโหนดที่ปิดหรือยืนยันระยะแล้วของตนเอง
เมื่อผ่อนคลายขอบ u → v ด้านหน้า จะลองปรับ distF[v] ให้เป็น distF[u] + c(u,v) ถ้าค่านี้ต่ำกว่าเดิม และบันทึก parentF[v] = u ส่วนด้านย้อนเมื่อประมวลผล v จะเดินตามขอบขาเข้าที่มาจาก u แล้วลองปรับ distB[u] เป็น c(u,v) + distB[v] พร้อมบันทึก nextB[u] = v ทิศของสูตรต่างกันเพราะแผนที่ต้นทุนด้านย้อนหมายถึงต้นทุนจากโหนดนั้นไปยังเป้าหมายในกราฟเดิม
เก็บ μ เป็นต้นทุนต่ำที่สุดของเส้นทางสมบูรณ์ที่ประกอบได้จากข้อมูลสองฝั่ง เริ่มต้นด้วยอนันต์ หาก s = t ให้คืนเส้นทางว่างที่มีต้นทุน 0 ทันที เมื่อฝั่งหน้าและฝั่งย้อนรู้ระยะของโหนดเดียวกัน v จะได้ผู้สมัคร distF[v] + distB[v] หากมีขอบเชื่อม u → v และรู้ distF[u] กับ distB[v] จะได้ผู้สมัคร distF[u] + c(u,v) + distB[v] ทั้งสองแบบสร้างเส้นทางจริงได้เมื่อป้ายระยะและตัวชี้พ่อแม่สอดคล้องกัน
เงื่อนไขหยุดและเหตุผล
กำหนด α และ β เป็นระยะต่ำสุดที่ยังใช้ได้ในคิวหน้าและคิวย้อนตามลำดับ หลังทิ้งรายการ stale แล้ว เงื่อนไขหยุดคือ α + β ≥ μ โดย μ ต้องมาจากเส้นทางสมบูรณ์ที่ตรวจสอบได้ สูตรนี้แสดงในเอกสารสอน University of Connecticut ในรูป min_i(g_i + r_i) ≤ Qf.peek() + Qr.peek() ซึ่งกลับข้างได้เป็นเงื่อนไขเดียวกัน เอกสาร UConn Lecture 7 (PDF)
เหตุผลอาศัยคุณสมบัติของ Dijkstra: เมื่อขยายโหนดที่มีระยะต่ำสุด โหนดที่ยังไม่ปิดในฝั่งนั้นจะมีระยะไม่น้อยกว่าค่าต่ำสุดในคิว ภายใต้ invariant ของการค้น หากยังมีเส้นทางที่ดีกว่า μ รอให้ต่อครบ มันต้องมีส่วนที่ยังเดินจาก s อย่างน้อย α และส่วนจากอีกด้านอย่างน้อย β ดังนั้นต้นทุนของเส้นทางที่ยังอาจปรับปรุงคำตอบจึงไม่น้อยกว่า α + β เมื่อผลรวมนี้ไม่ต่ำกว่า μ ก็ไม่มีเส้นทางที่ยังไม่พบสามารถชนะคำตอบ μ ได้ ค่านี้เป็นขอบเขตสำหรับการปรับปรุงที่ยังเป็นไปได้ตามสถานะการค้น ไม่ใช่การอ้างว่าระยะของทุกเส้นทางในกราฟไม่น้อยกว่า α + β
ข้อสำคัญคืออัปเดต μ จากผู้สมัครที่เพิ่งพบก่อนตรวจเงื่อนไขหยุดในรอบนั้น และคำนวณ α กับ β หลังลบคิว stale แล้ว การสลับว่าจะขยายฝั่งใดก่อนทำได้หลายแบบ เช่น เลือกด้านที่มีค่าต่ำสุด หรือสลับกัน แต่รูปแบบการสลับไม่ได้แทนที่การรับรองขอบเขตหยุด หากคิวฝั่งใดหมด แต่ยังไม่มี μ จำกัด ก็ไม่มีเส้นทางจาก s ไป t ตามกราฟที่ให้มา ถ้ามี μ จำกัดและขอบเขตหยุดผ่านแล้ว ให้คืนเส้นทางที่สร้างจากข้อมูลสองฝั่ง
ANALYSIS: μ เป็นคำตอบที่พบแล้ว จึงเป็นขอบเขตบน ไม่ควรตั้งให้เท่ากับ “ระยะของโหนดที่เพิ่งถูกแตะ” โดยไม่ประกอบเส้นทางครบ ส่วน α + β เป็นขอบเขตล่างของการปรับปรุงที่ยังเป็นไปได้ภายใต้สถานะการค้น ความถูกต้องมาจากการเปรียบเทียบขอบเขตสองชนิดนี้ ไม่ใช่จากตำแหน่งที่ search frontiers ดูเหมือนจะบรรจบกัน
การสร้างและตรวจเส้นทางผลลัพธ์
เมื่อหยุดแล้ว ให้สร้างครึ่งแรกจากจุดเชื่อมย้อนตาม parentF จนถึง s แล้วกลับลำดับ จากนั้นสร้างครึ่งหลังตาม nextB ไปจนถึง t ถ้าใช้ขอบข้าม u → v ให้ต่อเส้นทางหน้าไปถึง u แล้วตามด้วย v และส่วนย้อนจาก v กรณีจุดเชื่อมเป็นโหนดเดียวกัน ให้ใส่โหนดนั้นเพียงครั้งเดียว การต่อผิดทิศอาจทำให้โหนดซ้ำหรือสร้างเส้นทางที่ไม่มีขอบจริง
จากคำอธิบายสู่อินเทอร์แอกทีฟ
SIMULATION · BIDIRECTIONAL SEARCH EXPLORER
สำรวจการค้นสองฝั่งทีละรอบ
ดูกราฟเดิม คิวค้นหา และต้นทุนผู้สมัครที่เปลี่ยนไป กดขั้นถัดไปจนเงื่อนไขหยุดรับรองคำตอบ
สี Cyan: F settled · Amber: B settled · เขียว: เส้นทางผู้สมัคร · ลูกศรคงทิศเดิม
แบบจำลองกราฟคงที่ขนาดเล็ก ต้นทุนจำนวนเต็มไม่ติดลบ ไม่มี LLM การฝึกน้ำหนัก หรือผล benchmark
ตัวสำรวจกราฟควรให้ผู้ใช้เพิ่มโหนดและขอบพร้อมทิศทางและต้นทุน เลือก s กับ t แล้วแสดงดัชนีขาออกและขาเข้าคนละสี ระหว่างค้นให้แสดงคิวหน้าและคิวย้อน ระยะที่ใช้ได้หลังทิ้ง stale ค่า μ ปัจจุบัน เส้นทางผู้สมัคร และค่าของ α + β ในแต่ละจังหวะ เมื่อเงื่อนไขหยุดผ่าน ระบบควรอธิบายว่าผู้สมัครใดเป็นคำตอบที่ดีที่สุด และขอบเขตที่เหลือพิสูจน์อะไร
SIMULATION · SEARCH CERTIFICATE GAME
เกมยืนยันเส้นทางภายในงบ
เลือกขยายฝั่งเริ่มหรือฝั่งเป้าหมาย เป้าหมายคือยืนยันคำตอบที่ผ่านเงื่อนไขหยุดภายในงบ การพบกันครั้งแรกยังไม่พอ
สี Cyan: F settled · Amber: B settled · เขียว: เส้นทางผู้สมัคร · ลูกศรคงทิศเดิม
รอบที่ 0 ·
แบบจำลองกราฟคงที่ขนาดเล็ก ต้นทุนจำนวนเต็มไม่ติดลบ ไม่มี LLM การฝึกน้ำหนัก หรือผล benchmark
เปรียบเทียบกับ Dijkstra และ bidirectional BFS
| วิธี | เหมาะกับข้อมูลแบบใด | โครงสร้างหลัก | เงื่อนไขสำคัญ |
|---|---|---|---|
| Dijkstra ทิศเดียว | น้ำหนักไม่ติดลบ ต้องการระยะจากต้นทาง หรือไม่มีดัชนีขาเข้า | คิวลำดับความสำคัญหนึ่งชุด | หยุดเมื่อเป้าหมายถูกนำออกจากคิวด้วยระยะต่ำสุด |
| Bidirectional Dijkstra | คำถามจากต้นทางหนึ่งไปปลายทางหนึ่ง และเข้าถึงขอบย้อนกลับได้ | คิวและระยะสองชุด พร้อม μ | หยุดเมื่อ α + β ≥ μ หลังอัปเดตผู้สมัครและล้าง stale entries |
| Bidirectional BFS | กราฟไม่ถ่วงน้ำหนักหรือทุกขอบมีต้นทุนเท่ากัน | คิว FIFO และชั้นระยะสองด้าน | ใช้จำนวนขอบเป็นต้นทุน; อย่าใช้แทนน้ำหนักทั่วไป |
REPORTED CLAIM: งาน Goldberg และ Harrelson ปี 2005 เสนอ ALT ซึ่งผสาน A* กับ landmark bounds และรายงานผลทดลองของอัลกอริทึมที่ศึกษาในเครือข่ายถนนและกราฟสังเคราะห์ ผลดังกล่าวไม่ใช่ benchmark ที่บทความนี้ทำซ้ำ และไม่ควรนำมาอ้างเป็นตัวเลขความเร็วของโค้ด bidirectional Dijkstra ตัวอย่างนี้ เอกสาร NetworkX ระบุ API ของ bidirectional Dijkstra แต่ความเร็วในงานจริงยังขึ้นกับโครงสร้างกราฟ น้ำหนัก ตำแหน่งต้นทางปลายทาง และต้นทุนการสร้างหรือเก็บดัชนีขาเข้า
บางคำอธิบายใช้ภาพต้นไม้ที่มี branching factor คงที่ b และความลึก d เพื่อเปรียบเทียบการสำรวจประมาณ b^d กับสองฝั่งที่ลงลึกใกล้ d/2 ซึ่งเป็น intuition ในกรณีสมดุลเท่านั้น กราฟจริงอาจมีแขนงไม่เท่ากัน ทางแคบคดเคี้ยว น้ำหนักที่ต่างกัน หรือจุดเริ่มและจุดหมายใกล้กันมาก กรณีเช่นนี้การค้นสองด้านอาจลดงานเพียงเล็กน้อย หรือมี overhead เพิ่มจากคิวและการประกอบผลลัพธ์ จึงไม่ควรเขียนว่าลดความซับซ้อนหรือเวลาลงครึ่งหนึ่งในทุกกรณี
ตัวอย่างงานประยุกต์และขอบเขตของคำว่า planning
การค้นเส้นทางถนนเป็นตัวอย่างตรงไปตรงมา: โหนดแทนทางแยก ขอบแทนการเดินทางตามถนน และน้ำหนักอาจแทนระยะทางหรือเวลาที่คงที่สำหรับคำถามนั้น ระบบต้องกำหนดก่อนว่าขอบสะท้อนข้อจำกัดทิศทาง เช่น ทางวันเวย์หรือทางปิดอย่างไร หากน้ำหนักเปลี่ยนระหว่างการค้น ค่าระยะที่เก็บไว้อาจไม่สอดคล้องกับกราฟเดิมและต้องจัดการปัญหา dynamic shortest path แยกต่างหาก
คำว่า “planning” มีความหมายกว้างกว่า shortest path ในกราฟคงที่ บางระบบวางแผนต้องพิจารณาผลของการกระทำ เป้าหมายหลายข้อ ความไม่แน่นอน หรือการเปลี่ยนแปลงของโลก Bidirectional Dijkstra ไม่ได้สร้างแบบจำลองเหล่านี้ให้เอง และไม่รับรองว่าขอบที่ป้อนมาถูกต้อง มันรับประกันคุณสมบัติจำกัดอย่างหนึ่ง: เมื่อเงื่อนไขของกราฟและน้ำหนักเป็นไปตามข้อกำหนด จะคืนเส้นทางต้นทุนต่ำสุดตามกราฟนั้น
ความล้มเหลวที่ควรตรวจใน implementation
กรณีแรกคือหยุดเมื่อเจอโหนดร่วมครั้งแรก แล้วคืน μ โดยไม่ตรวจขอบเขตคิว กรณีนี้ให้คำตอบที่ถูกได้ในบางอินพุต แต่ไม่มีใบรับรองทั่วไป กรณีที่สองคือค้นย้อนด้วยขอบขาออกแทนขาเข้าในกราฟมีทิศทาง ผลลัพธ์อาจผิดทิศแม้ทุกระยะดูสมเหตุสมผล กรณีที่สามคือใช้ค่าคิวเก่าคำนวณ α หรือ β ซึ่งทำให้ lower bound ที่นำไปเทียบกับ μ ไม่ใช่ค่าปัจจุบัน
กรณีที่สี่คือรับน้ำหนักติดลบหรือใช้ Dijkstra กับกราฟที่มีต้นทุนเปลี่ยนระหว่างการค้น กรณีที่ห้าคือประกอบเส้นทางจาก parent ฝั่งย้อนโดยกลับทิศผิดหรือคิดต้นทุนขอบเชื่อมซ้ำ กรณีที่หกคือไม่ทดสอบกราฟไม่มีเส้นทาง ทำให้โปรแกรมคืนค่าอนันต์เหมือนเป็นคำตอบ กรณีที่เจ็ดคือจัดการขอบศูนย์และ tie ไม่รัดกุมจนตัวชี้ parent วนซ้ำหรือการตรวจเส้นทางค้าง
ข้อจำกัดและแนวทางต่อยอด
ข้อจำกัดแรกคือขอบต้องมีต้นทุนไม่ติดลบและกราฟต้องคงที่ตลอดการค้น ข้อจำกัดที่สองคือการค้นย้อนกลับต้องเข้าถึง predecessor ได้ถูกต้อง หากกราฟมาจากเครื่องมือภายนอกที่ให้เฉพาะการสร้างสถานะไปข้างหน้า การย้อนหาโหนดก่อนหน้าอาจมีต้นทุนสูงหรือทำไม่ได้ ข้อจำกัดที่สามคือการรับรองเป็นเรื่องความถูกต้องของเส้นทางในกราฟ ไม่ได้พิสูจน์ว่ากราฟแทนโลกจริงครบถ้วน
สรุปจำง่าย
- ใช้ Bidirectional Dijkstra กับคำถามจากต้นทางถึงปลายทางบนกราฟที่มีน้ำหนักไม่ติดลบ
- ฝั่งย้อนเริ่มที่เป้าหมาย แต่เดินตามขอบขาเข้าของกราฟเดิมด้วยต้นทุนเดิม
- การพบโหนดร่วมหรือขอบเชื่อมสร้างผู้สมัคร μ เท่านั้น ยังไม่ใช่เหตุผลหยุด
- ล้างรายการคิวที่ stale แล้วคำนวณ α และ β; หยุดเมื่อ
α + β ≥ μ - สร้างเส้นทางกลับจากตัวชี้ทั้งสองฝั่งและตรวจว่าทุกขอบมีอยู่จริงและผลรวมตรงกับ μ
- ถ้ากราฟไม่มีน้ำหนักหรือทุกขอบต้นทุนเท่ากัน ให้พิจารณา Bidirectional BFS; ถ้าน้ำหนักติดลบ อย่าใช้ Dijkstra
ร่องรอยการค้นควรเป็นบันทึกว่าโปรแกรมตรวจอะไรและหยุดด้วยเหตุผลใด ไม่ใช่หลักฐานว่าโมเดลหรือระบบ “คิด” เหมือนมนุษย์ ความน่าเชื่อถือมาจากแบบจำลองที่ถูกต้อง เงื่อนไขอัลกอริทึมที่ครบถ้วน และการตรวจผลลัพธ์ที่ทำซ้ำได้
คำถามที่พบบ่อย
หยุดทันทีเมื่อค้นจากสองด้านเจอกันได้ไหม
ไม่ได้สำหรับ weighted bidirectional Dijkstra แบบทั่วไป การพบกันยืนยันว่ามีเส้นทางและให้ต้นทุนผู้สมัคร แต่ยังมีเส้นทางอื่นที่ถูกกว่าและยังไม่ถูกค้นพบได้ ให้ค้นต่อจน α + β ≥ μ
ทำไมกราฟมีทิศทางต้องมีดัชนีขาเข้า
เพราะการค้นย้อนจาก t ต้องหาว่าโหนดใดมีขอบเข้าสู่โหนดปัจจุบันในกราฟเดิม การเดินตามขอบขาออกเดิมจาก t จะตอบคำถามคนละทิศทาง และอาจสร้างเส้นทางที่เดินไม่ได้จาก s ไป t
ใช้กับน้ำหนักศูนย์ได้หรือไม่
ได้ เพราะศูนย์ไม่ติดลบ แต่ต้องจัดการเส้นทางต้นทุนเท่ากันและวงจรศูนย์ไม่ให้ตัวชี้ย้อนวน การคืนเส้นทางสั้นที่สุดหนึ่งเส้นอาจใช้ tie-breaking ที่กำหนดแน่นอน
ถ้าไม่มีทางจากต้นทางไปเป้าหมายเกิดอะไรขึ้น
ถ้าคิวฝั่งหนึ่งหมดและยังไม่มีผู้สมัครเส้นทางสมบูรณ์ที่มีต้นทุนจำกัด ให้รายงานว่าไม่มีเส้นทาง ไม่ควรคืน ∞ เป็นระยะทางปกติหรือสร้างเส้นทางว่างโดยไม่มีเงื่อนไข
Bidirectional Dijkstra เร็วกว่า Dijkstra เสมอไหม
ไม่เสมอ ความคุ้มขึ้นกับรูปร่างและน้ำหนักของกราฟ จุดเริ่มและเป้าหมาย รวมถึงค่าใช้จ่ายในการสร้างและเก็บขอบย้อน ในกราฟบางแบบการค้นสองด้านช่วยลดงาน แต่ไม่มีการรับประกันความเร็วเหนือกว่าทุกอินพุต
แหล่งอ้างอิง
- Goldberg และ Harrelson, “Computing the Shortest Path: A* Search Meets Graph Theory,” SODA 2005 (PDF) — พื้นฐาน Dijkstra บนขอบไม่ติดลบ การค้นบนกราฟย้อนกลับ วิธีเก็บเส้นทางผู้สมัคร μ และทฤษฎีบทความถูกต้องของ bidirectional algorithm; รายงานผลทดลองบนกลุ่มกราฟที่ระบุในงาน
- University of Connecticut, Lecture 7: Shortest Path Algorithms (PDF) — เอกสารสอนที่แสดงเงื่อนไขหยุดด้วยค่าต่ำสุดของระยะร่วมเทียบกับผลรวมค่าต่ำสุดในคิวสองฝั่ง และตัวอย่างค่าใน heap
- Holte และคณะ, “Bidirectional Search That Is Guaranteed to Meet in the Middle,” AAAI 2016 — งาน MM สำหรับ bidirectional heuristic search ซึ่งเป็นอัลกอริทึมคนละแบบกับตัวอย่าง Dijkstra ในบทความนี้
- เอกสาร NetworkX:
bidirectional_dijkstra— รูปแบบ API การคืนระยะและเส้นทาง การจัดการ no path และคำเตือนเรื่องน้ำหนักติดลบหรือทศนิยม - เอกสาร NetworkX: Shortest Paths — ประเภทอัลกอริทึม shortest path และข้อกำหนดทิศทางของกราฟ
ใส่ความเห็น