อัลกอริทึมของ Bellman Ford ทำงานโดย ประเมินความยาวของเส้นทางจากจุดยอดเริ่มต้นไปยังจุดยอดอื่นๆ มากเกินไป จากนั้นจึงค่อยผ่อนคลายการประมาณการเหล่านั้นโดยค้นหาเส้นทางใหม่ที่สั้นกว่าเส้นทางที่ประเมินไว้ก่อนหน้านี้
ทำไมอัลกอริทึมของ Bellman-Ford ถึงทำงาน
อัลกอริทึมของ Bellman Ford ทำงานโดย ประเมินความยาวของเส้นทางจากจุดยอดเริ่มต้นไปยังจุดยอดอื่นๆ มากเกินไป จากนั้นจึงค่อยผ่อนคลายการประมาณการเหล่านั้นโดยค้นหาเส้นทางใหม่ที่สั้นกว่าเส้นทางที่ประเมินไว้ก่อนหน้านี้
Bellman Ford ทำงานตลอดเวลาหรือไม่
มันง่ายที่จะเห็นว่าอัลกอริทึมของ Bellman-Ford สามารถ ทำให้จุดยอดทั้งหมดผ่อนคลายอย่างไม่รู้จบ ของวงจรนี้และจุดยอดที่สามารถเข้าถึงได้จากจุดนั้นดังนั้น หากคุณไม่จำกัดจำนวนเฟสเป็น n-1 อัลกอริทึมจะทำงานไปเรื่อย ๆ และปรับปรุงระยะห่างจากจุดยอดเหล่านี้อย่างต่อเนื่อง
ทำไม Bellman Ford Run N 1 ครั้ง?
สิ่งที่เราทำใน BellmanFord คือ เราคลายขอบของความยาวเส้นทาง 1 จากนั้นในการวนซ้ำครั้งถัดไป เราจะคลายขอบของความยาวเส้นทาง 2 ……ดังนั้นต่อไปจนกว่าเราจะคลายขอบของเส้นทาง ความยาว n-1 ดังนั้นการวนซ้ำจึงทำงานเป็น n-1 ครั้ง
Bellman Ford เป็นอัลกอริธึมที่โลภหรือเปล่า
อัลกอริธึมของ Bellman Ford ทำงานเมื่อมีขอบน้ำหนักติดลบ และยังตรวจจับวงจรน้ำหนักติดลบอีกด้วย อัลกอริทึมของ Dijkstra ไม่ทำงานเมื่อมีขอบน้ำหนักติดลบ … มีการใช้แนวทาง Dynamic Programming เพื่อนำอัลกอริธึมไปใช้ แนวทางโลภถูกนำมาใช้ อัลกอริทึม