ปัญหาวิถีสั้นสุด

ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (อังกฤษ: shortest path problem)​ เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้นๆ

วิถีสั้นสุดบนกราฟไม่ระบุทิศทางที่ไม่ถ่วงน้ำหนักระหว่างจุดยอด 6 กับ 1 คือ (6, 4, 5, 1)

นิยาม แก้

ปัญหาวิถีสั้นสุดอาจแตกต่างกันออกไป ตามแต่ประเภทของกราฟที่กำลังจะดำเนินการ เช่น กราฟระบุทิศทาง/กราฟไม่ระบุทิศทาง/กราฟผสม หรือ กราฟถ่วงน้ำหนัก/กราฟไม่ถ่วงน้ำหนัก เป็นต้น วิถีสั้นสุดจากจุดยอด u ไป v คือวิถีที่มีจุดเริ่มต้นที่ u และจบที่ v โดยที่ผลรวมของน้ำหนักในวิถีนั้นน้อยที่สุดในบรรดาวิถีทั้งหมดจาก u ไป v สำหรับกราฟไม่ถ่วงน้ำหนัก นิยามให้วิถีสั้นสุดคือวิถีที่มีเส้นเชื่อมน้อยที่สุด

โดยทั่วไป ปัญหาวิถีสั้นสุดจะกำหนดจุดยอด u และ v มาให้และให้หาวิถีสั้นสุดระหว่างจุดยอดทั้งคู่ เรียกปัญหานี้ว่าปัญหาวิถีสั้นสุดแบบคู่เดียว นอกจากนี้ยังมีปัญหาวิถีสั้นสุดอยู่ด้วยกันอีก 3 รูปแบบ คือ

  • ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอด v ไปจุดยอดอื่นๆทั้งหมดในกราฟ
  • ปัญหาวิถีสั้นสุดแบบแหล่งปลายทางเดียว เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอดทั้งหมดมาที่จุดยอด v ปัญหานี้ในกรณีของกราฟไม่ระบุทิศทางสามารถแก้ได้ทันทีโดยมองปลายทางเป็นต้นทาง แล้วแก้ไขปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแทน ในกรณีกราฟระบุทิศทางก็สามารถลดรูปปัญหามาเป็นปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวได้เช่นกัน โดยกลับเส้นเชื่อมจากจุดยอด a ไป b เป็น b ไป a ก่อน แล้วแก้ไขปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวจาก v แทน
  • ปัญหาวิถีสั้นสุดแบบทุกคู่ เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจาก u ไป v สำหรับทุกๆจุดยอด u , v ภายในกราฟ

สังเกตว่าปัญหาแต่ละรูปแบบสามารถแก้ได้โดยการแก้ปัญหาวิถีสั้นสุดแบบคู่เดียวหลายๆครั้ง อย่างไรก็ตาม การแก้ไขปัญหาในแต่ละรูปแบบมีวิธีการที่แตกต่างกันออกไปซึ่งทำให้มีประสิทธิภาพมากกว่าการแก้ปัญหาปัญหาวิถีสั้นสุดแบบคู่เดียวหลายๆครั้ง

อันที่จริง ณ ปัจจุบัน ยังไม่มีขั้นตอนวิธีใดที่กรณีเลวร้ายสุดสามารถแก้ปัญหาวิถีสั้นสุดแบบคู่เดียวโดยที่มีประสิทธิภาพด้านเวลามากกว่าปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวได้[1] ดังนั้นเมื่อต้องการแก้ปัญหาวิถีสั้นสุดแบบคู่เดียว โดยทั่วไปก็จะแก้ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวจนได้คำตอบที่ต้องการและจบขั้นตอนวิธี อย่างไรก็ตาม สำหรับกราฟพิเศษบางประเภทสามารถแก้ปัญหาวิถีสั้นสุดแบบคู่เดียวโดยการคำนวณล่วงหน้าได้ เช่น กราฟต้นไม้ กราฟเส้นตรง กราฟวัฏจักรเดียว เป็นต้น[ต้องการอ้างอิง]

ขั้นตอนวิธี แก้

ขั้นตอนวิธีในการแก้ปัญหาวิถีสั้นสุด จะใช้แนวคิดของการการคลายเส้นเชื่อม (relaxation) นั่นคือขณะเริ่มต้น คำตอบวิถีสั้นสุดจะยังไม่ถูกต้อง เส้นเชื่อม e จะเรียกว่า ตึง (tense) ถ้าสามารถใช้ e แล้วทำให้มีวิถีที่น้ำหนักรวมร้อยกว่าคำตอบที่มีอยู่ ดังนั้นขั้นตอนวิธีแก้ปัญหาวิถีสั้นสุดก็จะทำการคลายเส้นเชื่อมที่ตึง นั่นคือใช้เส้นเชื่อมที่ตึงเพื่อให้ได้คำตอบของวิถีสั้นสุดที่ดียิ่งขึ้นเรื่อยๆ สุดท้ายเมื่อไม่พบเส้นเชื่อมที่ตึงก็แปลว่าวิถีที่ได้เป็นวิถีสั้นสุดแล้ว[2]

ปัญหาวิถีสั้นสุดมองแต่เพียงการไปถึงได้ของจุดยอดต่างๆเท่านั้น ดังนั้นสำหรับกราฟไม่ระบุทิศทางจึงสามารถแปลงเป็นกราฟระบุทิศทางได้ โดยการเปลี่ยนเส้นเชื่อมไม่มีทิศทาง เป็นเส้นเชื่อมมีทิศทาง 2 เส้นที่มีทิศทั้งไปและกลับ

สำหรับกราฟไม่ถ่วงน้ำหนัก จากนิยามที่กำหนดให้วิถีสั้นสุดคือมีจำนวนเส้นเชื่อมในวิถีน้อยที่สุด ดังนั้นจึงอาจกล่าวได้ว่าเส้นเชื่อมทุกเส้นมีความสำคัญเท่ากัน กล่าวคือกราฟไม่ถ่วงน้ำหนักจะเทียบเท่ากับกราฟถ่วงน้ำหนักที่เส้นเชื่อมทุกเส้นมีน้ำหนักเท่ากันและไม่เป็นลบ ตัวอย่างเช่นกราฟถ่วงน้ำหนักหนึ่งหน่วย (unit-weight graph) เป็นต้น[2]

ขั้นตอนวิธีในการแก้ปัญหาที่ได้รับความนิยมและสำคัญมีดังนี้

ขั้นตอนวิธีอื่นๆและการนำมาใช้งานในรูปแบบต่างๆอาจหาได้ที่ Cherkassky et al[3]

ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว แก้

ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวเป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอด v ไปจุดยอดอื่นๆทั้งหมดในกราฟ ได้ต้นไม้วิถีสั้นสุดออกมาเป็นผลลัพธ์

กราฟถ่วงน้ำหนักหนึ่งหน่วย แก้

กราฟอวัฏจักรระบุทิศทางสำหรับเส้นเชื่อมน้ำหนักใดๆ แก้

กราฟที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ แก้

ขั้นตอนวิธี ความซับซ้อนทางด้านเวลา ผู้คิดค้น
O(V4) Shimbel 1955
O(V2EL) Ford 1956
ขั้นตอนวิธีของเบลแมน-ฟอร์ด O(VE) Bellman 1958, Moore 1959
O(V2 log V) Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
ขั้นตอนวิธีของไดค์สตรา O(V2) Leyzorek et al. 1957, Dijkstra 1959
... ... ...
ขั้นตอนวิธีของไดค์สตราพร้อมใช้ฮีปฟีโบนัชชี O(E + V log V) Fredman & Tarjan 1984, Fredman & Tarjan 1987
O(E log log L) Johnson 1982, Karlsson & Poblete 1983
Gabow's algorithm O(V logE/V L) Gabow 1983b, Gabow 1985b
O(E + V√log L) Ahuja et al. 1990

กราฟเชิงระนาบที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ แก้

กราฟสำหรับเส้นเชื่อมน้ำหนักใดๆ แก้

กราฟเชิงระนาบสำหรับเส้นเชื่อมน้ำหนักใดๆ แก้

ปัญหาวิถีสั้นสุดแบบทุกคู่ แก้

กราฟสำหรับเส้นเชื่อมน้ำหนักใดๆ แก้

การนำไปใช้งาน แก้

ปัญหาที่เกี่ยวข้อง แก้

การมองด้วยกำหนดการเชิงเส้น แก้

เนื้อหาที่เกี่ยวข้อง แก้

อ้างอิง แก้

หมายเหตุ แก้

บรรณานุกรม แก้

อ่านเพิ่ม แก้

  • Frigioni, D.; Marchetti-Spaccamela, A.; Nanni, U. (1998). "Fully dynamic output bounded single source shortest path problem". Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms. Atlanta, GA. pp. 212–221. CiteSeerX 10.1.1.32.9856.
  • Dreyfus, S. E. (October 1967). An Appraisal of Some Shortest Path Algorithms (PDF) (Report). Project Rand. United States Air Force. RM-5433-PR. เก็บ (PDF)จากแหล่งเดิมเมื่อ November 17, 2015. DTIC AD-661265.