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

ขั้นตอนวิธีของจอห์นสัน () เป็นขั้นตอนวิธีที่ทำการปรับกราฟไม่ให้มีน้ำหนักติดลบเพื่อให้สามารถใช้ขั้นตอนวิธีของไดค์สตราได้ในการหาเส้นทางสั้นที่สุดระหว่างทุกคู่จุดหรือปม ซึ่งเป็นขั้นตอนวิธีที่เหมาะในการใช้กับกราฟระบุทิศทางที่มีเส้นเชื่อมน้อยเพราะถ้าเส้นเชื่อมเยอะจะช้ากว่า ขั้นตอนวิธีของฟลอยด์-วอร์แชล แต่ต้องไม่มีวงรอบที่น้ำหนักติดลบอยู่ด้วย ผู้คิดค้นวิธีการนี้คือ โดนัลด์ บี. จอห์นสัน(Donald B. Johnson) ซึ่งเผยแพร่เป็นครั้งแรกเมื่อ ค.ศ. 1977

 การอธิบายขั้นตอนวิธี 
ขั้นตอนวิธีของจอห์นสันประกอบด้วยขั้นตอนต่อไปนี้
 สร้างจุดหรือปม ใหม่ขึ้นหนึ่งจุดลงในกราฟ และสร้างเส้นเชื่อมจากจุดใหม่ที่เพิ่มมาไปยังจุดอื่นทุกจุด โดยกำหนดน้ำหนักทั้งหมดเป็น 0
 ใช้ขั้นตอนวิธีของเบลล์แมน-ฟอร์ดจากจุดใหม่ หาน้ำหนักน้อยที่สุดจากจุดใหม่ไปยังทุกจุดแต่ละจุดก็เก็บค่าไว้ ถ้าตรวจพบวงจร ที่มีน้ำหนักติดลบ ให้หยุดการทำงาน
 แปลงกราฟดั้งเดิมไม่ให้มีน้ำหนักติดลบ โดยใช้ค่าที่เก็บไว้ในของแต่ละจุดที่คำนวณได้จากขั้นตอนวิธีของเบลล์แมน-ฟอร์ด กล่าวคือ เส้นเชื่อมจากจุด ก ไปยังจุด ข เดิมมีน้ำหนักเป็น น้ำหนักเส้นเชื่อม(ก,ข) เปลี่ยนค่าน้ำหนักใหม่ของเส้นเชื่อมเส้นนั้นเป็น น้ำหนักเส้นเชื่อม(ก,ข) + ค่าที่เก็บไว้ใน ก − ค่าที่ีเก็บไว้ใน ข
 สุดท้ายใช้ขั้นตอนวิธีของไดค์สตรา เพื่อหาเส้นทางสั้นที่สุดจากจุดใดจุดต้นทางหนึ่ง ไปยังจุดอื่นในกราฟที่แปลงน้ำหนักแล้วได้

 ตัวอย่าง 

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

 อ้างอิง 
 .
 .

 การออกแบบและวิเคราะห์อัลกอริทึม สมชาย ประสิทธิ์จูตระกูล 
หมวดหมู่:ขั้นตอนวิธี