ขั้นตอนวิธีของจอห์นสัน
บทความนี้อาจต้องการตรวจสอบต้นฉบับ ในด้านไวยากรณ์ รูปแบบการเขียน การเรียบเรียง คุณภาพ หรือการสะกด คุณสามารถช่วยพัฒนาบทความได้ |
ขั้นตอนวิธีของจอห์นสัน (อังกฤษ: Johnson's algorithm) เป็นขั้นตอนวิธีที่ทำการปรับกราฟไม่ให้มีน้ำหนักติดลบเพื่อให้สามารถใช้ขั้นตอนวิธีของไดค์สตราได้ในการหาเส้นทางสั้นที่สุดระหว่างทุกคู่จุดหรือปม ซึ่งเป็นขั้นตอนวิธีที่เหมาะในการใช้กับกราฟระบุทิศทางที่มีเส้นเชื่อมน้อยเพราะถ้าเส้นเชื่อมเยอะจะช้ากว่า ขั้นตอนวิธีของฟลอยด์-วอร์แชล แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย ผู้คิดค้นวิธีการนี้คือ โดนัลด์ บี. จอห์นสัน(Donald B. Johnson) ซึ่งเผยแพร่เป็นครั้งแรกเมื่อ ค.ศ. 1977
การอธิบายขั้นตอนวิธี แก้
ขั้นตอนวิธีของจอห์นสันประกอบด้วยขั้นตอนต่อไปนี้
- สร้างจุดหรือปม ใหม่ขึ้นหนึ่งจุดลงในกราฟ และสร้างเส้นเชื่อมจากจุดใหม่ที่เพิ่มมาไปยังจุดอื่นทุกจุด โดยกำหนดน้ำหนักทั้งหมดเป็น 0
- ใช้ขั้นตอนวิธีของเบลล์แมน-ฟอร์ดจากจุดใหม่ หาน้ำหนักน้อยที่สุดจากจุดใหม่ไปยังทุกจุดแต่ละจุดก็เก็บค่าไว้ ถ้าตรวจพบวงจร ที่มีน้ำหนักติดลบ ให้หยุดการทำงาน
- แปลงกราฟดั้งเดิมไม่ให้มีน้ำหนักติดลบ โดยใช้ค่าที่เก็บไว้ในของแต่ละจุดที่คำนวณได้จากขั้นตอนวิธีของเบลล์แมน-ฟอร์ด กล่าวคือ เส้นเชื่อมจากจุด ก ไปยังจุด ข เดิมมีน้ำหนักเป็น น้ำหนักเส้นเชื่อม(ก,ข) เปลี่ยนค่าน้ำหนักใหม่ของเส้นเชื่อมเส้นนั้นเป็น น้ำหนักเส้นเชื่อม(ก,ข) + ค่าที่เก็บไว้ใน ก − ค่าที่ีเก็บไว้ใน ข
- สุดท้ายใช้ขั้นตอนวิธีของไดค์สตรา เพื่อหาเส้นทางสั้นที่สุดจากจุดใดจุดต้นทางหนึ่ง ไปยังจุดอื่นในกราฟที่แปลงน้ำหนักแล้วได้
ตัวอย่าง แก้
เริ่มจากตอนแรกได้ข้อมูลของกราฟเส้นเชื่อมที่มีน้ำหนักติดลบ จากนั้นทำการเพิ่มจุดใหม่ q ที่มีเส้นเชื่อมน้ำหนักเป็น 0 ชี้ไปยังทุกจุดที่มีก่อนในตอนแรก แล้วจึงใช้ขั้นตอนวิธีของเบลล์แมน-ฟอร์ดโดยใช้ q เป็นจุดเริ่มต้น จะได้ค่า h(v) ที่ที่สั้นที่สุดจาก q ไปยังจุด v จากนั้นทำการเปลี่ยนน้ำหนักของเส้นเชื่อมแต่ละเส้น w(u,v) ให้เป็นบวกทุกเส้นเป็น w(u,v) + h(u) − h(v) หลังจากได้กราฟที่ทำการแปลงน้ำหนักแล้วก็สามารถใช้ขั้นตอนวิธีของไดค์สตราหาวิถีสั้นสุดได้
รหัสเทียม แก้
Johnson ( graph G ) {
//สร้างกราฟ K ใหม่เพิ่มปมพิเศษ q และเพิ่มเส้นเชื่อมจากปม q ไปปมอื่นทุกปมให้น้ำหนักเป็น 0
create graph K : K.V = G.V add {q} //V คือ จุดปม
: K.E = G.E add {(q,i) | i in G.V} //E คือ เส้นเชื่อม
: K.W = G.W , K.W(q,i) = 0 | i in G.V //W คือ ระยะระหว่างปมสองปม
BellmanFord(K,q) //ถ้ามีวงจรติดลบจะหยุด
for each edge (i,j)in G.E
G.W(i,j) += h[i]-h[j]
for each vertex i in G.V {
d=dijkstra(G,i) //d คือ array ของทุกจุดในกราฟแต่ละจุดเก็บระยะสั้นสุดจากจุด i
for each vertex j in G.V
L(i,j)=d[j]-(h[i]-h[j]) //L คือ ระยะทางสั้นสุด
}
return L
}
ความถูกต้อง แก้
เมื่อพิจารณาวิถีจากปม ก ถึง ข แม้แต่ละวิถีจะผ่านปมต่างกันแต่ความยาวที่เพิ่มขึ้นจะเท่ากันเสมอ
- ความยาวใหม่(ก→จ→ฉ→ข) = ความยาวเดิม(ก→จ→ฉ→ข) + ค่าระยะทางที่เก็บไว้ของ(ก)- ค่าระยะทางที่เก็บไว้ของ(ข)
- ความยาวใหม่(ก→ช→ข) = ความยาวเดิม(ก→ช→ข) + ค่าระยะทางที่เก็บไว้ของ(ก)- ค่าระยะทางที่เก็บไว้ของ(ข)
ดังนั้นวิถีสั้นสุดจะเป็นวิถีเดิม ความยาวของวงจรในกราฟก็ไม่เปลี่ยน
- ความยาวใหม่(ก→จ→ฉ→ก) = ความยาวเดิม(ก→จ→ฉ→ก) + ค่าระยะทางที่เก็บไว้ของ(ก)- ค่าระยะทางที่เก็บไว้ของ(ก)
ประสิทธิภาพเชิงเวลา แก้
v คือ จำนวนปม e คือ จำนวนเส้นเชื่อม ถ้า ขั้นตอนวิธีของไดค์สตรา ใช้ binary heap จะทำให้ Johnson ใช้เวลา ซึ่งเมื่อใช้กับ กราฟที่มีเส้นเชื่อมน้อยๆ จะเร็วกว่าใช้ ขั้นตอนวิธีของฟลอยด์-วอร์แชล ที่ใช้ O(v3)
เพิ่มเติม แก้
- ULearn การออกแบบอัลกอริทึม (สมชาย ประสิทธิ์จูตระกูล)
- วิดีโอประกอบคำอธิบาย
- ขั้นตอนวิธีของไดค์สตรา เป็นขั้นตอนวิธีที่ใช้ในการหาระยะทางเส้นทางสั้นสุดของคู่ปมใดๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ
- ขั้นตอนวิธีของเบลแมน-ฟอร์ด เป็นขั้นตอนที่ใช้ในการคำนวณหาวิถีที่สั้นสุดแบบแหล่งต้นทางเดียวในกราฟที่มีการถ่วงน้ำหนักของเส้นเชื่อมเป็นบวก หรือน้ำหนักของเส้นเชื่อมเป็นลบ
- ขั้นตอนวิธีของฟลอยด์-วอร์แชล เป็นขั้นตอนวิธีการวิเคราะห์กราฟเพื่อที่จะหาระยะทางของเส้นทางสั้นสุดในกราฟที่มีน้ำหนักของเส้นเชื่อมเป็นบวก หรือ น้ำหนักของเส้นเชื่อมเป็นลบ แต่ไม่สามารถหาได้ถ้ามีวงจรลบ
อ้างอิง แก้
- Black, Paul E., "Johnson's Algorithm", Dictionary of Algorithms and Data National Institute of Standards and Technology.
- Suurballe, J. W. (1974), "Disjoint paths in a network", Networks, 14: 125–145, doi:10.1002/net.3230040204.