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

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

## แนวคิด

* ใช้ได้กับ กราฟที่มีน้ำหนักของเส้นเชื่อมทั้งบวกและลบ แต่ไม่สามารถใช้ได้กับ กราฟที่มีวงจรลบ
* คืนค่า ระยะทางของเส้นทางที่สั้นสุดของทุกๆคู่ปม
* ใช้กำหนดการพลวัต กำหนดการพลวัต แบบล่างขึ้นบน ()
* 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) )

thumb|left|600px

### คำอธิบาย

* 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

หมวดหมู่:ขั้นตอนวิธีกราฟ
หมวดหมู่:ปัญหาฟังก์ชันพหุนาม
หมวดหมู่:กำหนดการพลวัต