ขั้นตอนวิธีของฟลอยด์-วอร์แชล

ขั้นตอนวิธีของฟลอยด์-วอร์แชล (อังกฤษ: Floyd–Warshall algorithm) หรือที่รู้จักในนามว่า ขั้นตอนวิธีของฟลอยด์, ขั้นตอนของรอย-วอร์แชล หรือ ขั้นตอนวิธีของรอย-ฟลอยด์ เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส่นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ ก็ได้แต่ไม่สามารถหาได้ถ้ามีวงจรลบ โดยการทำงานหนึ่งครั้งของขั้นตอนวิธีนี้จะได้คำตอบของระยะทางของเส้นทางสั้นสุดของทุกๆคู่ปมบนกราฟ อย่างไรก็ตามจะไม่สามารถคืนค่ารายละเอียดของเส้นทางสั้นสุดในแต่ละคู่ปมได้ ยกเว้นมีการเพิ่มเติมเข้าไป ขั้นตอนวิธีนี้เป็นตัวอย่างของกำหนดการพลวัตแบบด้านล่างขึ้นด้านบน โดยขั้นตอนวิธีนี้ถูกคิดขึ้นโดย โรเบิร์ต ฟลอยด์ ในปี 1962 อย่างไรก็ตามขั้นตอนวิธีนี้มีส่วนสำคัญเหมือนกับอัลกอริทึมของเบอร์นาร์ด รอยด์ ในปี 1959 และของสตีเฟน วอร์แชล ในปี 1962 ในการค้นหา ความสัมพันธ์แบบถ่ายทอดของกราฟ (อังกฤษ: Transitive closure)

ใกล้เคียง

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

แหล่งที่มา

WikiPedia: ขั้นตอนวิธีของฟลอยด์-วอร์แชล http://quickgraph.codeplex.com/ http://www.codeplex.com/quickgraph http://www.cplusplus.happycodings.com/Algorithms/c... http://julmis.julmajanne.com/index.php/FloydWarsha... http://www.mathworks.com/matlabcentral/fileexchang... http://www.microshell.com/programming/computing-de... http://www.microshell.com/programming/floyd-warsha... http://tide4javascript.com/?s=Floyd http://www.youtube.com/watch?v=Cadt4OYXpJQ http://www.youtube.com/watch?v=Sygq1e0xWnM