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

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

แนวคิด

  • ใช้ได้กับ กราฟที่มีน้าหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับ กราฟที่มีวงจรลบ
  • คืนค่า ระยะทางของเส้นทางที่สั้นสุดของทุกๆคู่ปม
  • ใช้กำหนดการพลวัต กำหนดการพลวัต แบบล่างขึ้นบน (อังกฤษ: Bottom-up)
  • path (i,j,0) คือ ไม่มีปมระหว่างทาง จึงมีค่าเท่ากับระยะทางจาก i ไป j


ภาษาอื่น ๆ