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

ขั้นตอนวิธีของฟลอยด์-วอร์แชล  หรือที่รู้จักในนามว่า ขั้นตอนวิธีของฟลอยด์, ขั้นตอนของรอย-วอร์แชล หรือ ขั้นตอนวิธีของรอย-ฟลอยด์ เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส่นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ ก็ได้แต่ไม่สามารถหาได้ถ้ามีวงจรลบ โดยการทำงานหนึ่งครั้งของขั้นตอนวิธีนี้จะได้คำตอบของระยะทางของเส้นทางสั้นสุดของทุกๆคู่ปมบนกราฟ อย่างไรก็ตามจะไม่สามารถคืนค่ารายละเอียดของเส้นทางสั้นสุดในแต่ละคู่ปมได้ ยกเว้นมีการเพิ่มเติมเข้าไป ขั้นตอนวิธีนี้เป็นตัวอย่างของกำหนดการพลวัตแบบด้านล่างขึ้นด้านบน โดยขั้นตอนวิธีนี้ถูกคิดขึ้นโดย โรเบิร์ต ฟลอยด์ ในปี 1962 อย่างไรก็ตามขั้นตอนวิธีนี้มีส่วนสำคัญเหมือนกับอัลกอริทึมของเบอร์นาร์ด รอยด์ ในปี 1959 และของสตีเฟน วอร์แชล ในปี 1962 ในการค้นหา ความสัมพันธ์แบบถ่ายทอดของกราฟ 
ขั้นตอนวิธี.
ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้ในการเปรียบเทียบระยะทางเส้นทางทั้งหมดที่เป็นไปได้ของกราฟระหว่างแต่ละคู่ของปม โดยมีอัตราการเติบโตของการทำงานเป็น "Θ (|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))
รหัสเทียม.
สะดวกเมื่อคำนวณ กรณีที่ 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]<0 เมื่อ i มีค่าเท่ากับ j แสดงว่ามีวงจรลบ จะไม่สามารถหาคำตอบได้
 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]) ;
 15 ตั้งแต่ i := 1 ถึง
 16 ถ้า path[i][i] < 0 เมื่อนั้น
 17 มีวงจรติดลบอยู่
การสร้างเส้นทาง.
ขั้นตอนวิธีของฟลอยด์-วอร์แชลนั้นโดยปกติแล้วจะหาแค่ระยะทางของเส้นทางที่สั้นที่สุดของแต่ละคู่ปม แต่สามารถปรับเปลี่ยนเพิ่มเติมส่วนของการจำเส้นทางที่ผ่านระหว่างทางได้ด้วยโดยการ เพิ่ม 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) ;
การวิเคราะห์อัตราการเติบโต.
เพื่อที่จะหา shortest path ของคู่ปมจำนวน n^2 คู่ปม จาก path (i,j,k-1) ต้องการ 2n^2 คำสั่ง เนื่องจากเราเริ่มจาก path (i,j,0) = edgeCost (i,j) และคำนวณ path (i,j,1) , path (i,j,2), ..., path (i,j,n) ดังนั้นเราจึงได้คำสั่งรวมเท่ากับ n · 2n^2 = 2n^3 จึงสรุปได้ว่ามีอัตราการเติบโตเป็น Θ (n^3).
การนำไปใช้งาน.
ขั้นตอนวิธีของฟลอยด์-วอร์แชลนั้นสามารถนำไปแก้ปัญหาปัญหาต่างๆได้ดังนี้
บันทึก.
จากขั้นตอนวิธีของฟลอยด์-วอร์แชล จะเห็นได้ว่ามีประโยชน์มากในการนำมาหาเส้นทางสั้นสุดของทุกคู่ปม เนื่องจากประสิทธิภาพโดยรวมนั้น เป็น Θ (|V|^3) ซึ่งถ้าเทียบกับ
ขั้นตอนวิธีของไดค์สตรา O (V* (|E|+|V|log|V|)) และของ ขั้นตอนวิธีของเบลแมน-ฟอร์ด O (V* (|V||E|)) ในกรณีแย่สุด E ประมาณได้ V^2 นั้น
จะเห็นได้ว่ามีประสิทธิภาพที่ดีกว่า
การเขียนโปรแกรม.
การเขียนโปรแกรม สามารถทำได้หลายภาษามากมาย .
<math>\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}</math>
D[k] และ n[k] เมื่อ กราฟถูกคำนวณด้วยขั้นตอนวิธีนี้