ปัญหาวิถีสั้นสุด
จากวิกิพีเดีย สารานุกรมเสรี
ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (อังกฤษ: shortest path problem) เป็นปัญหาที่ต้องการหาวิถีระหว่างจุดยอด 2 จุดภายในกราฟ โดยที่ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้นๆ
ปัญหาวิถีสั้นสุดมีอยู่ 3 รูปแบบ
- ปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียว เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอด v ไปจุดยอดอื่นๆทั้งหมดในกราฟ
- ปัญหาวิถีสั้นสุดแบบแหล่งปลายทางเดียว เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจากจุดยอดทั้งหมดมาที่จุดยอด v ปัญหานี้ในกรณีของกราฟไม่ระบุทิศทางสามารถแก้ได้ทันทีโดยมองปลายทางเป็นต้นทาง แล้วแก้ไขปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวแทน ในกรณีกราฟระบุทิศทางก็สามารถลดรูปปัญหามาเป็นปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวได้เช่นกัน โดยกลับเส้นเชื่อมจากจุดยอด a ไป b เป็น b ไป a ก่อน แล้วแก้ไขปัญหาวิถีสั้นสุดแบบแหล่งต้นทางเดียวจาก v แทน
- ปัญหาวิถีสั้นสุดแบบทุกคู่ เป็นปัญหาที่ต้องการหาวิถีสั้นสุดจาก u ไป v สำหรับทุกๆจุดยอด u , 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 |
[แก้] ปัญหาวิถีสั้นสุดแบบทุกคู่
- ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้เวลา O(V3)
- ขั้นตอนวิธีของจอห์นสัน ใช้เวลา O(V2log V + VE)
[แก้] เนื้อหาที่เกี่ยวข้อง
[แก้] อ้างอิง
- แม่แบบ:Introduction to Algorithms
- D. Frigioni; A. Marchetti-Spaccamela and U. Nanni (1998). "Fully dynamic output bounded single source shortest path problem". Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms: 212-221
[แก้] ดูเพิ่ม
- Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs". Numerische Mathematik 1 (ฉบับที่): 269–271. doi:10.1007/BF01386390. http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf.
- 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. http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934.
- 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. http://portal.acm.org/citation.cfm?id=28874.
- 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.
- 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): 285–292, Cambridge: Harvard University Press
