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

ขั้นตอนวิธีของฟลอยด์-วอร์แชล (Floyd–Warshall algorithm) หรือที่รู้จักในนามว่า ขั้นตอนวิธีของฟลอยด์, ขั้นตอนของรอย-วอร์แชล หรือ ขั้นตอนวิธีของรอย-ฟลอยด์ เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส่นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ ก็ได้แต่ไม่สามารถหาได้ถ้ามีวงจรลบ โดยการทำงานหนึ่งครั้งของขั้นตอนวิธีนี้จะได้คำตอบของระยะทางของเส้นทางสั้นสุดของทุกๆคู่ปมบนกราฟ อย่างไรก็ตามจะไม่สามารถคืนค่ารายละเอียดของเส้นทางสั้นสุดในแต่ละคู่ปมได้ ยกเว้นมีการเพิ่มเติมเข้าไป ขั้นตอนวิธีนี้เป็นตัวอย่างของกำหนดการพลวัตแบบด้านล่างขึ้นด้านบน โดยขั้นตอนวิธีนี้ถูกคิดขึ้นโดย โรเบิร์ต ฟลอยด์ ในปี 1962 อย่างไรก็ตามขั้นตอนวิธีนี้มีส่วนสำคัญเหมือนกับอัลกอริทึมของเบอร์นาร์ด รอยด์ ในปี 1959 และของสตีเฟน วอร์แชล ในปี 1962 ในการค้นหา ความสัมพันธ์แบบถ่ายทอดของกราฟ (Transitive closure)
== แนวคิด ==
ใช้ได้กับ กราฟที่มีน้ำหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับ กราฟที่มีวงจรลบ
คืนค่า ระยะทางของเส้นทางที่สั้นสุดของทุกๆคู่ปม
ใช้กำหนดการพลวัต กำหนดการพลวัต แบบล่างขึ้นบน (Bottom-up)
path (i,j,0) คือ ไม่มีปมระหว่างทาง จึงมีค่าเท่ากับระยะทางจาก i ไป j
== ขั้นตอนวิธี ==
ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้ในการเปรียบเทียบระยะทางเส้นทางทั้งหมดที่เป็นไปได้ของกราฟระหว่างแต่ละคู่ของปม โดยมีอัตราการเติบโตของการทำงานเป็น "Θ (|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 ไป j
path (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 โดยสามารถเขียนทับข้อมูลที่เคยบันทึกไว้จากการคำนวณของกรณีที่ผ่านมา k-1 หมายความว่าใช้พื้นที่ในการเก็บข้อมูลในหน่วยความจำเพียงแค่สมการกำลังสอง หรือเพียง อาเรย์สองมิติ นั่นเอง
1  /* สมมุติให้ฟังก์ชัน edgeCost (i,j) คืนค่า น้ำหนักของเส้นเชื่อมจาก i ไป j
2  */
3
4  จำนวนเต็ม path[][];
5  /* อาเรย์ 2 มิติ path[i][j] เป็นเส้นทางสั้นที่สุดจากปม i ไป j โดยใช้ ปมเริ่มต้น (1..k−1).
6  ในแต่ละขั้นตอนของ ขั้นตอนวิธี  โดยแต่ละ path[i][j] มีค่าเริ่มต้นคือ  edgeCost (i,j).
7  */
8
9  /* ขั้นตอนวิธีของฟลอยด์-วอร์แชล */
10   ขั้นตอน  ฟลอยด์-วอร์แชล 
11      ตั้งแต่ k := 1 ถึง n
12        ตั้งแต่ i := 1 ถึง n
13           ตั้งแต่ j := 1 ถึง n
14              path[i][j] = ค่าน้อยที่สุด ( path[i][j], path[i][k]+path[k][j] ) ;
== พฤติกรรมเมื่อเจอวงจรติดลบ ==
วงจรติดลบ คือ วงจรที่มีผลรวมของระยะทางของเส้นเชื่อมเป็นค่าลบ ระยะทางสั้นสุดไม่สามารถกำหนดได้เนื่องจาก เส้นทางสามารถติดลบไปเรื่อยๆ ก็จะน้อยลงเรื่อยไม่มีที่สิ้นสุด สำหรับ ขั้นตอนวิธีของฟลอยด์-วอร์แชล นั้นจะสังเกตวงจรลบได้จาก path[i][j] เมื่อ i มีค่าเท่ากับ j โดยถ้า path[i][j]\begin{align}&D^{(0)}=\begin{pmatrix}0&3&8&\infty&-4\\\infty&0&\infty&1&7\\\infty&4&0&\infty&\infty\\2&\infty&-5&0&\infty\\\infty&\infty&\infty&6&0\end{pmatrix}\quad&\Pi^{(0)}=\begin{pmatrix}\text{NIL}&1&1&\text{NIL}&1\\\text{NIL}&\text{NIL}&\text{NIL}&2&2\\\text{NIL}&3&\text{NIL}&\text{NIL}&\text{NIL}\\4&\text{NIL}&4&\text{NIL}&\text{NIL}\\\text{NIL}&\text{NIL}&\text{NIL}&5&\text{NIL}\end{pmatrix}\\ \\&D^{(1)}=\begin{pmatrix}0&3&8&\infty&-4\\\infty&0&\infty&1&7\\\infty&4&0&\infty&\infty\\2&5&-5&0&-2\\\infty&\infty&\infty&6&0\end{pmatrix}&\Pi^{(1)}=\begin{pmatrix}\text{NIL}&1&1&\text{NIL}&1\\\text{NIL}&\text{NIL}&\text{NIL}&2&2\\\text{NIL}&3&\text{NIL}&\text{NIL}&\text{NIL}\\4&1&4&\text{NIL}&1\\\text{NIL}&\text{NIL}&\text{NIL}&5&\text{NIL}\end{pmatrix}\\ \\&D^{(2)}=\begin{pmatrix}0&3&8&4&-4\\\infty&0&\infty&1&7\\\infty&4&0&5&11\\2&5&-5&0&-2\\\infty&\infty&\infty&6&0\end{pmatrix}&\Pi^{(2)}=\begin{pmatrix}\text{NIL}&1&1&2&1\\\text{NIL}&\text{NIL}&\text{NIL}&2&2\\\text{NIL}&3&\text{NIL}&2&2\\4&1&4&\text{NIL}&1\\\text{NIL}&\text{NIL}&\text{NIL}&5&\text{NIL}\end{pmatrix}\\ \\&D^{(3)}=\begin{pmatrix}0&3&8&4&-4\\\infty&0&\infty&1&7\\\infty&4&0&5&11\\2&-1&-5&0&-2\\\infty&\infty&\infty&6&0\end{pmatrix}&\Pi^{(3)}=\begin{pmatrix}\text{NIL}&1&1&2&1\\\text{NIL}&\text{NIL}&\text{NIL}&2&2\\\text{NIL}&3&\text{NIL}&2&2\\4&3&4&\text{NIL}&1\\\text{NIL}&\text{NIL}&\text{NIL}&5&\text{NIL}\end{pmatrix}\\ \\&D^{(4)}=\begin{pmatrix}0&3&-1&4&-4\\3&0&-4&1&-1\\7&4&0&5&3\\2&-1&-5&0&-2\\8&5&1&6&0\end{pmatrix}&\Pi^{(4)}=\begin{pmatrix}\text{NIL}&1&4&2&1\\4&\text{NIL}&4&2&1\\4&3&\text{NIL}&2&1\\4&3&4&\text{NIL}&1\\4&3&4&5&\text{NIL}\end{pmatrix}\\ \\&D^{(5)}=\begin{pmatrix}0&1&-3&2&-4\\3&0&-4&1&-1\\7&4&0&5&3\\2&-1&-5&0&-2\\8&5&1&6&0\end{pmatrix}&\Pi^{(5)}=\begin{pmatrix}\text{NIL}&3&4&5&1\\4&\text{NIL}&4&2&1\\4&3&\text{NIL}&2&1\\4&3&4&\text{NIL}&1\\4&3&4&5&\text{NIL}\end{pmatrix}\end{align}
D[k] และ n[k] เมื่อ กราฟถูกคำนวณด้วยขั้นตอนวิธีนี้
== ดูเพิ่ม ==
Lec 19 | MIT 6.046J / 18.410J Introduction to Algorithms All pairs Shortest path clip 
Lecture MIT shortest path 
Java implementation at Algo wiki  
ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
ภาพเคลื่อนไหว ขั้นตอนวิธีของฟลอยด์-วอร์แชล
Robert Sedgewick 
อัลกอริทึม : 06-11 (2/3)
ขั้นตอนวิธีของไดค์สตรา เป็นขั้นตอนวิธีที่ใช้ในการหาระยะทางเส้นทางสั้นสุดของคู่ปมใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ
ขั้นตอนวิธีของจอห์นสัน เป็นขั้นตอนวิธีที่ใช้หาเส้นทางสั้นที่สุดระหว่างทุกคู่จุด ในกราฟระบุทิศทางที่มีเส้นเชื่อมน้อย ขั้นตอนวิธีนี้สามารถใช้น้ำหนักของเส้นเชื่อมเป็นจำนวนลบได้ แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย
== อ้างอิง ==
การออกแบบและวิเคราะห์อัลกอริทึม สมชาย ประสิทธิ์จูตระกูล 
Floyd–Warshall_algorithm 
FloydWarshal Computer Science at Biola  
Floyd-warshall 
== แหล่งข้อมูลอื่น ==
Algorithm Design, first semester, 2010 (นัทที นิภานันท์) 
การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
Analyze Floyd's algorithm in an online Javascript IDE 
Interactive animation of the Floyd–Warshall algorithm
The Floyd–Warshall algorithm in C#, as part of QuickGraph 
Visualization of Floyd's algorithm
ขั้นตอนวิธีกราฟ
ปัญหาฟังก์ชันพหุนาม
กำหนดการพลวัต