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

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

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

## อ้างอิง
* .
* .

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