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

ขั้นตอนวิธีของฟลอยด์-วอร์แชลนั้นโดยปกติแล้วจะหาแค่ระยะทางของเส้นทางที่สั้นที่สุดของแต่ละคู่ปม แต่สามารถปรับเปลี่ยนเพิ่มเติมส่วนของการจำเส้นทางที่ผ่านระหว่างทางได้ด้วยโดยการ เพิ่ม next[i][j] ที่เอาไว้จำค่า ปมที่ผ่านระหว่างทางที่ทำให้มีค่าระยะทางเส้นทางสั้นสุดของคู่ปมมากที่สุด โดย next[i][j] จะได้รับการเปลี่ยนค่าไปเรื่อยๆ ถ้าเกิด ปมที่ผ่านระหว่างทางของแต่ละคู่ปมต้นทางปลายทางที่สนใจอยู่ ทำให้เกิดระยะทางสั้นสุดระหว่างคู่ปมนั้น

 1 ขั้นตอน ฟลอยด์-วอร์แชลกับการสร้างเส้นทาง () 2    ตั้งแต่ k := 1 ถึง n 3       ตั้งแต่ i := 1 ถึง n 4          ตั้งแต่ j := 1 ถึง n 5             ถ้า path[i][k] + path[k][j] < path[i][j] เมื่อนั้น 6                path[i][j] := path[i][k]+path[k][j]; 7                next[i][j] := k; 8 9  ขั้นตอน GetPath (i,j)10    ถ้า path[i][j] เท่ากับอนันต์  เมื่อนั้น11       คืนค่า "ไม่มีเส้นทาง";12    จำนวนเต็ม ค่ากลาง := next[i][j];13    ถ้า ค่ากลางเท่ากับ  null เมื่อนั้น14       คืนค่า ""  /* มีเส้นเชื่อมจาก i ไป j ที่ไม่มีปมอยู่ระหว่างเส้นเชื่อมนั้น */15    มิฉะนั้น16       คืนค่า GetPath (i,ค่าเริ่มต้น) + ค่ากลาง + GetPath (ค่าเริ่มต้น,j) ;


ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด 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