ขั้นตอนวิธีของเบลแมน-ฟอร์ด
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
บทความนี้ได้รับแจ้งให้ปรับปรุงหลายข้อ กรุณาช่วยปรับปรุงบทความ หรืออภิปรายปัญหาที่หน้าอภิปราย
|
ขั้นตอนวิธีของเบลแมน-ฟอร์ด (อังกฤษ: Bellman-Ford Algorithm) เป็นขั้นตอนวิธีที่ใช้ในการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวสำหรับเส้นเชื่อมที่มีน้ำหนักใดๆ นอกจากนี้ขั้นตอนวิธียังสามารถตรวจพบวัฏจักรที่มีน้ำหนักรวมของเส้นเชื่อมเป็นลบ หรือที่เรียกว่าวัฏจักรเชิงลบ (อังกฤษ: Negative cycle) ซึ่งทำให้ปัญหาวิถีสั้นสุดไม่นิยาม ขั้นตอนวิธีนี้ถูกคิดค้นโดยนักพัฒนาชื่อริชาร์ด เบลแมน (Richard Bellman) และเลสเตอร์ ฟอร์ด จูเนียร์ (Lester Ford Jr)
| ประเภท | ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว |
|---|---|
| โครงสร้างข้อมูล | กราฟ |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
| ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | |
แนวคิด แก้
ขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นมีแนวคิดดังนี้
- ใช้ได้กับกราฟที่มีน้ำหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับกราฟที่มีวงจรเชิงลบ
- กรณีที่ในกราฟนั้นมีวงจรเชิงลบจะแจ้งให้ผู้ใช้ทราบ
- ใช้กำหนดการพลวัต
- วิถีสั้นสุดจาก s ไป t ต้องไม่ผ่านปมซ้ำ และมีเส้นเชื่อมในวิถีอย่างมาก |v|-1 เส้น เมื่อ v แทนเส้นเชื่อมทั้งหมดในกราฟนั้น
ขั้นตอนวิธี แก้
ขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นอยู่ในโครงสร้างพื้นฐานที่คล้ายกับขั้นตอนวิธีของไดค์สตรา โดยมีอัตราการเติบโตของการทำงานเป็น "O(|V||E|)" เมื่อ |V| และ |E| คือจำนวนปมและเส้นเชื่อมของกราฟนั้นๆ ตามลำดับ
เริ่มต้นพิจารณาจากแนวคิดพื้นฐานง่ายๆว่าเส้นทางที่สั้นที่สุดที่ไปยังปมทั้งหมดนั้นเป็นอนันต์ จากนั้นทำสัญลักษณ์ว่าได้ความยาวของเส้นทางเป็นศูนย์ ดังภาพ
จากนั้นพยายามเดินไปตามเส้นทางในทุกเส้นเชื่อมของกราฟระบุทิศทาง ถ้าพบว่าเมื่อไปตามเส้นเชื่อมนั้นแล้วตึงก็ให้พยายามที่จะผ่อนมัน
การผ่อนเส้นเชื่อมของกราฟ หมายถึง การตรวจสอบเพื่อดูว่าเส้นทางที่ไปยังปมนั้นไม่สามารถสั้นลงได้(เมื่อดูจากน้ำหนักของแต่ละเส้นเชื่อม) จากตัวอย่างกราฟข้างต้น เริ่มแรกเมื่อตรวจสอบที่เส้นทางจากปมที่ 1 ไปยังปมที่ 2 พบว่ามีน้ำหนักเส้นเชื่อมคือ 6 ซึ่งเป็นความยาวของเส้นทางที่สั้นที่สุดจากปมที่ 1 ไปยังปมที่ 2 ที่มีค่าน้อยกว่าอนันต์ ดังนั้นจึงแทนค่าอนันต์ในปมที่ 2 ด้วย 6 และเมื่อพิจารณาเส้นทางจากปมที่ 1 ไปยังปมที่ 4 พบว่ามีน้ำหนักเส้นเชื่อมคือ 7 ซึ่งเป็นความยาวของเส้นทางที่สั้นที่สุดจากปมที่ 1 ไปยังปมที่ 4 ที่มีค่าน้อยกว่าอนันต์ ดังนั้นจึงแทนค่าอนันต์ในปมที่ 4 ด้วย 7
ทำตามขั้นตอนนี้ไปเรื่อนๆเป็นจำนวน n - 1 ครั้ง เมื่อ n แทนจำนวนปมทั้งหมดในกราฟที่พิจารณา ดังนั้นในตัวอย่างนี้จะต้องใช้ขั้นตอนดังกล่างนี้ 4 ครั้ง ดังภาพ
รหัสเทียม แก้
ข้อมูลนำเข้า คือ กราฟระบุทิศทางที่เส้นเชื่อมมีน้ำหนักที่มี v ปม
ข้อมูลส่งออก คือ ป้าย D[u] สำหรับปม u ใดๆบนกราฟ โดย D[u] คือระยะทางจากปม v ถึงปม u บนกราฟ ซึ่งกราฟนี้ต้องไม่มีวงจรเชิงลบ
1 กำหนดให้ D[v] มีค่าเท่ากับ 0 2 ตั้งแต่ แต่ละปม u ไม่เท่ากับปม v ในกราฟ G 3 กำหนดให้ D[u] มีค่าเป็นอนันต์ 4 ตั้งแต่ i := 1 ถึง n-1 5 ตั้งแต่ ทุกเส้นเชื่อมที่ออกจากปม z 6 ถ้า (D[u]+w(u,z))<D[z] 7 จะให้ D[z]เก็บค่า D[u]+w(u,z) //w(u,z) คือการดำเนินการของการผ่อนเส้นเชื่อมกราฟ 8 ถ้าไม่มีเส้นเชื่อมใดเลยที่ถูกผ่อน 9 จะคืนค่าระยะทางจากปม v ถึงปม u ของแต่ละปม u 10 ไม่เช่นนั้น 11 จะคืนกลับมาว่า"กราฟนี้มีวงจรเชิงลบ"
การวิเคราะห์อัตราการเติบโต แก้
จากรหัสเทียมข้างต้นจะพบว่าการดำเนินการของขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นจะมีการทำงานอยู่ 2 ส่วนหลัก คือ
- วงวนที่มีการวนเพื่อตรวจสอบความตึงของน้ำหนักเส้นเชื่อมในกราฟ ซึ่งจะทำงานเป็นเวลานานเท่าจำนวนเส้นเชื่อมที่มี ดังนั้น จะใช้เวลาในการทำงานส่วนนี้เป็น O(|E|) เมื่อ E คือจำนวนเส้นเชื่อมของกราฟหนึ่งๆ
- ส่วนการทำงานที่ต้องผ่านปมทุกปมในกราฟจะใช้เวลาทั้งหมดเป็น O(|V|) เมื่อ V คือจำนวนปมของกราฟหนึ่งๆ
เพราะฉะนั้นจึงสรุปได้ว่าชั้นตอนวิธีของเบลแมน-ฟอร์ดมีอัตราการเติบโตเท่ากับ O(|V||E|)
การนำไปใช้งาน แก้
- วิถีสั้นสุดในกราฟมีทิศทาง
- โพรโตคอลเลือกเส้นทางแบบตารางระยะทาง (RIP)
ตัวอย่างรหัสในภาษาต่างๆ แก้
- C
- C++ เก็บถาวร 2011-10-06 ที่ เวย์แบ็กแมชชีน
- Java เก็บถาวร 2013-02-17 ที่ เวย์แบ็กแมชชีน
- PHP เก็บถาวร 2011-09-12 ที่ เวย์แบ็กแมชชีน
- Python
ดูเพิ่ม แก้
- ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
- ภาพเคลื่อนไหว ขั้นตอนวิธีของเบลแมน-ฟอร์ด
- Bellman-ford Algorithm E-leaning(Introduction to Algorithms)
- ขั้นตอนวิธีของไดค์สตรา เป็นขั้นตอนวิธีที่ใช้ในการหาระยะทางเส้นทางสั้นสุดของคู่ปมใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ
- ขั้นตอนวิธีของจอห์นสัน เป็นขั้นตอนวิธีที่ใช้หาเส้นทางสั้นที่สุดระหว่างทุกคู่จุด ในกราฟระบุทิศทางที่มีเส้นเชื่อมน้อย ขั้นตอนวิธีนี้สามารถใช้น้ำหนักของเส้นเชื่อมเป็นจำนวนลบได้ แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย
- ขั้นตอนวิธีของฟลอยด์-วอร์แชล เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส้นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ แต่ไม่สามารถหาได้ถ้ามีวงจรลบ