Floyd-Warshall สำหรับทุกคู่

บางครั้งคุณต้องการเส้นทางสั้นที่สุดระหว่างโหนดทุกคู่ ไม่ใช่เพียงจากจุดเริ่มต้นเดียว นั่นคือปัญหาเส้นทางระหว่างทุกคู่

ฟลอยด์–วอร์แชลล์เติมตารางระยะทางเต็มรูปแบบสำหรับโหนดทุกคู่ด้วยลูปซ้อนกันสามชั้นที่เป็นระเบียบ และแทบไม่ต้องเตรียมข้อมูล

ใช้เมทริกซ์ที่ dist[i][j] คือค่าใช้จ่ายที่ดีที่สุดจาก i ไป j โดยเริ่มต้นจากเส้นเชื่อมโดยตรงที่โจทย์ให้มา

โหนดทุกโหนดสามารถไปยังตัวเองได้โดยไม่มีค่าใช้จ่าย ดังนั้นให้กำหนดเส้นทแยงมุม dist[i][i] เป็นศูนย์ก่อนเริ่มปรับปรุงระยะทาง

เคล็ดลับคือ อนุญาตให้เส้นทางผ่านโหนดตัวกลาง k แล้วตรวจสอบว่าการเดินทางผ่าน k มีค่าใช้จ่ายน้อยกว่าการไปโดยตรงหรือไม่

ลูปด้านนอกสุดคือ k ซึ่งเป็นจุดกึ่งกลางที่เลือกไว้ ส่วนลูปด้านใน i และ j จะลองโหนดทุกคู่โดยเทียบกับจุดกึ่งกลางนั้น

สำหรับแต่ละคู่ ให้ปรับปรุงระยะทางผ่าน k หากเส้นทางจาก i ไป k แล้วไป j สั้นกว่า ให้ปรับ dist[i][j] เป็นค่าใช้จ่ายรวมดังกล่าว

เมื่อประมวลผล k เสร็จแล้ว ทุกคู่อาจใช้โหนดตัวกลางที่มีหมายเลขไม่เกิน k การวาง k ไว้ในลูปด้านนอกสุดจึงช่วยให้เงื่อนไขนี้ถูกต้อง

ฟลอยด์–วอร์แชลล์รองรับเส้นเชื่อมติดลบ แต่ไม่รองรับวงจรติดลบ วงจรติดลบจะทำให้ค่าบางรายการบนเส้นทแยงมุมต่ำกว่าศูนย์

ลูปสามชั้นบนโหนดจำนวน n โหนดทำให้ใช้เวลา O(n^3) และใช้พื้นที่ O(n^2) ซึ่งเหมาะในทางปฏิบัติเฉพาะเมื่อ n มีค่าไม่กี่ร้อย

เลือกฟลอยด์–วอร์แชลล์เมื่อกราฟมีขนาดเล็กและหนาแน่น และคุณต้องการระยะทางระหว่างทุกคู่จริง ๆ ไม่ใช่จากจุดเริ่มต้นเดียว

ลูปใดต้องอยู่ด้านนอกสุดในฟลอยด์–วอร์แชลล์

เริ่มต้นเมทริกซ์ กำหนดเส้นทแยงมุมเป็นศูนย์ จากนั้นวนลูป k, i, j และปรับปรุงระยะทางผ่าน k เพื่อหาเส้นทางสั้นที่สุดระหว่างทุกคู่ในเวลา O(n^3) 🧮