แนวคิด ของ ขั้นตอนวิธีของเบลแมน-ฟอร์ด

ขั้นตอนวิธีของเบลแมน-ฟอร์ดนั้นมีแนวคิดดังนี้

  • ใช้ได้กับกราฟที่มีน้ำหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับกราฟที่มีวงจรเชิงลบ
  • กรณีที่ในกราฟนั้นมีวงจรเชิงลบจะแจ้งให้ผู้ใช้ทราบ
  • ใช้กำหนดการพลวัต
  • วิถีสั้นสุดจาก s ไป t ต้องไม่ผ่านปมซ้ำ และมีเส้นเชื่อมในวิถีอย่างมาก |v|-1 เส้น เมื่อ v แทนเส้นเชื่อมทั้งหมดในกราฟนั้น

ใกล้เคียง

แหล่งที่มา

WikiPedia: ขั้นตอนวิธีของเบลแมน-ฟอร์ด http://codefat.com/2009/11/bellman-ford-algorithm-... http://compprog.wordpress.com/2007/11/29/one-sourc... http://compprog.files.wordpress.com/2007/11/bellma... http://www.youtube.com/watch?v=L6x53Vjy_HM http://www.people.vcu.edu/~dprimeau/cmsc502/posted... http://ww3.algorithmdesign.net/sample/ch07-weights... http://www.algowiki.net/wiki/index.php?title=Bellm... http://www.dreamincode.net/code/snippet2170.htm http://videolectures.net/mit6046jf05_demaine_lec18... http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_...