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

ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (อังกฤษ: 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 ภายในกราฟ

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

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

ขั้นตอนวิธี

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

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

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

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

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

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

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

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

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

• ทำการค้นตามแนวกว้าง ใช้เวลา O(V + E)

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

• ทำการเรียงเชิงทอพอโลยีและกำหนดการพลวัต ใช้เวลา O(V + E)

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

ขั้นตอนวิธี	ความซับซ้อนทางด้านเวลา	ผู้คิดค้น
	O(V^4)	Shimbel 1955
	O(V^2EL)	Ford 1956
ขั้นตอนวิธีของเบลแมน-ฟอร์ด	O(VE)	Bellman 1958, Moore 1959
	O(V^2 log V)	Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
ขั้นตอนวิธีของไดค์สตรา	O(V^2)	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

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

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

• ขั้นตอนวิธีของเบลแมน-ฟอร์ด

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

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

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

• ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้เวลา O(V³) เหมาะสำหรับกราฟหนาแน่นและนำมาใช้งานได้ง่ายมาก
• ขั้นตอนวิธีของจอห์นสัน ใช้เวลา O(V²log V + VE) เหมาะสำหรับกราฟไม่หนาแน่นซึ่งเวลาการทำงานจะดีกว่าการใช้ขั้นตอนวิธีของฟลอยด์-วอร์แชลเป็นอย่างมาก

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

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

• ปัญหาวิถีสั้นสุดบนระนาบแบบยุคลิด

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

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

• การไหลในเครือข่าย
• ต้นไม้วิถีสั้นสุด
• ปัญหาวิถีสั้นสุดบนระนาบแบบยุคลิด
• การค้นแบบสองทิศทาง ขั้นตอนวิธีหาวิถีสั้นสุดแบบคู่เดียว

อ้างอิง

1. http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:shortest-paths-algorithms
2. http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/index.htm โดย สมชาย ประสิทธิ์จูตระกูล
3. Cherkassky, Boris V.; Goldberg, Andrew V.; Radzik, Tomasz (1996). "Shortest paths algorithms: theory and experimental evaluation". Mathematical Programming. Ser. A. 73 (2): 129–174. doi:10.1016/0025-5610(95)00021-6. MR 1392160.CS1 maint: ref=harv (link)
4. http://xlinux.nist.gov/dads/HTML/dagShortPath.html

• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "Single-Source Shortest Paths and All-Pairs Shortest Paths". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 580–642. ISBN 0-262-03293-7.
• D. Frigioni (1998). "Fully dynamic output bounded single source shortest path problem". Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms. Atlanta, GA. pp. 212–-221. Unknown parameter |coauthors= ignored (|author= suggested) (help); C1 control character in |pages= at position 4 (help)

ดูเพิ่ม

• Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.CS1 maint: ref=harv (link)
• Fredman, Michael Lawrence; Tarjan, Robert E. (1984). "Fibonacci heaps and their uses in improved network optimization algorithms". 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. doi:10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.CS1 maint: ref=harv (link)
• Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms". Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874.CS1 maint: ref=harv (link)
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S. R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology.CS1 maint: ref=harv (link)
• Moore, E.F. (1959). "The shortest path through a maze". Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press. pp. 285–292.CS1 maint: ref=harv (link)