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

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


 คำอธิบาย 

 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]<0 เมื่อ i มีค่าเท่ากับ j แสดงว่ามีวงจรลบ จะไม่สามารถหาคำตอบได้

 เริ่มต้น ความยาวของเส้นทาง (i,i) เป็น 0
 เส้นทาง {(i,k), (k,i)} สามารถเปลี่ยนไปเรื่อยๆ
 หลังจากทำขั้นตอนวิธีนี้แล้ว (i,i) จะเป็นลบ ถ้ามี เส้นทางความยาวติดลบมาจาก i
 ถ้ามีความยาวจาก i กลับมา i เป็นลบ จะได้ว่า ระยะทางสั้นสุดที่ได้ผ่านปมระหว่างทางมามีค่าน้อยกว่า 0 จะเรียกว่าวงจรลบ

  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).

 การนำไปใช้งาน 

ขั้นตอนวิธีของฟลอยด์-วอร์แชลนั้นสามารถนำไปแก้ปัญหาปัญหาต่างๆได้ดังนี้

 วิถีสั้นสุดในกราฟมีทิศทาง
 ความสัมพันธ์แบบถ่ายทอด (Transitive closure) ของ กราฟมีทิศทาง
 การกำหนดเส้นทางที่เหมาะสมที่สุด
 การผกผันของเมทริกซ์จริง
 ตรวจสอบว่า กราฟไม่มีทิศทาง เป็นกราฟสองส่วนหรือไม่
 การคำนวณหาเส้นทางของเครือข่าย
 คำนวณหาเส้นทางที่มีปริมาณข้อมูลใดๆ ที่จะผ่านเข้า/ออกช่องทางสัญญาณหนึ่งๆได้ในระยะเวลาที่กำหนดมากที่สุด ในเครือข่าย

 บันทึก 
จากขั้นตอนวิธีของฟลอยด์-วอร์แชล จะเห็นได้ว่ามีประโยชน์มากในการนำมาหาเส้นทางสั้นสุดของทุกคู่ปม เนื่องจากประสิทธิภาพโดยรวมนั้น เป็น Θ (|V|^3) ซึ่งถ้าเทียบกับ
ขั้นตอนวิธีของไดค์สตรา O (V* (|E|+|V|log|V|) ) และของ ขั้นตอนวิธีของเบลแมน-ฟอร์ด O (V* (|V||E|)) ในกรณีแย่สุด E ประมาณได้ V^2 นั้น
จะเห็นได้ว่ามีประสิทธิภาพที่ดีกว่า

 ตัวอย่างรหัสในภาษาต่างๆ 
 Java 
 C 
 C++
 Perl
 PHP 

 การเขียนโปรแกรม 

การเขียนโปรแกรม สามารถทำได้หลายภาษามากมาย :en:programming language.
 สำหรับ C++, อยู่ใน boost::graph library
 สำหรับ C#, ที่ QuickGraph
 สำหรับ :en:Clojure, ที่ paste.lisp.org 
 สำหรับ Java, อยู่ใน Apache commons graph  library, หรือที่ Algowiki 
 สำหรับ MATLAB, อยู่ใน Matlab_bgl  package
 สำหรับ Perl, อยู่ใน Graph module
 สำหรับ PHP, บน page  and :en:PL/pgSQL, บน page  at Microshell
 สำหรับ Python, อยู่ใน :en:NetworkX library
 สำหรับ R, ใน e1017
 สำหรับ Ruby, ใน script

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

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