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

ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้ในการเปรียบเทียบระยะทางเส้นทางทั้งหมดที่เป็นไปได้ของกราฟระหว่างแต่ละคู่ของปม โดยมีอัตราการเติบโตของการทำงานเป็น "Θ (|V|^3)"

พิจารณากราฟ G กับปม V ตั้งแต่ปม 1 ถึง ปม N พิจารณาฟังก์ชัน shortestPath (i,j,k) ที่จะคืนค่าระยะทางของเส้นทางสั้นสุดที่เป็นไปได้จาก i ไป j โดยมีปม 1,2,3,...,k เท่านั้นที่เป็นปมระหว่างทางได้และ path (i,j,k) สามารถหาได้มาจาก path (i,j,k-1) หรือ path (i,k,k-1) +path (k,j,k-1) โดยดูว่าค่าไหนน้อยกว่ากัน และมีกรณีพื้นฐานคือpath (i,j,0) คือ ระยะทางโดยตรงจาก i ไป j ที่ไม่มีปมระหว่างทางนั่นเองจึงสามารถเขียนได้เป็น การเวียนเกิด ได้ดังนี้

path (i,j,0) = ระยะทางจาก i ไป jpath (i,j,k) = ค่าน้อยสุด (path (i,j,k-1),path (i,k,k-1) +path (k,j,k-1) )


คำอธิบาย


  • path (i,j,k) คือ ระยะทางของเส้นทางสั้นสุดจากปม i ไป j โดยมีปมที่อยู่ระหว่างทางได้คือ {1,2,3,...,k}
  • path (i,j,k-1) คือ ระยะทางของเส้นทางสั้นสุดจากปม i ไป j โดยมีปมที่อยู่ระหว่างทางได้คือ {1,2,3,...,k-1}
  • path (i,k,k-1) คือ ระยะทางของเส้นทางสั้นสุดจากปม i ไป kโดยมีปมที่อยู่ระหว่างทางได้คือ {1,2,3,...,k-1}
  • path (k,j,k-1) คือ ระยะทางของเส้นทางสั้นสุดจากปม k ไป j โดยมีปมที่อยู่ระหว่างทางได้คือ {1,2,3,...,k-1}


ใกล้เคียง

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