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

ขั้นตอนวิธีของเบลแมน-ฟอร์ด (อังกฤษ: Bellman-Ford Algorithm) เป็นขั้นตอนวิธีที่ใช้ในการแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวสำหรับเส้นเชื่อมที่มีน้ำหนักใดๆ นอกจากนี้ขั้นตอนวิธียังสามารถตรวจพบวัฏจักรที่มีน้ำหนักรวมของเส้นเชื่อมเป็นลบ หรือที่เรียกว่าวัฏจักรเชิงลบ (อังกฤษ: Negative cycle) ซึ่งทำให้ปัญหาวิถีสั้นสุดไม่นิยาม ขั้นตอนวิธีนี้ถูกคิดค้นโดยนักพัฒนาชื่อริชาร์ด เบลแมน (Richard Bellman) และเลสเตอร์ ฟอร์ด จูเนียร์ (Lester Ford Jr)

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

ประเภท ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว
โครงสร้างข้อมูล กราฟ
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด O ( | V | ) {\displaystyle O(|V|)}
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด O ( | V | | E | ) {\displaystyle O(|V||E|)}

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธี ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของเบลแมน-ฟอร์ด

แหล่งที่มา

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_...