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

ขั้นตอนวิธี

ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้ในการเปรียบเทียบระยะทางเส้นทางทั้งหมดที่เป็นไปได้ของกราฟระหว่างแต่ละคู่ของปม โดยมีอัตราการเติบโตของการทำงานเป็น "Θ (|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] ) ;

การสร้างเส้นทาง

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