ขั้นตอนวิธีของจอห์นสัน

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