บทความนี้ไม่มีจาก |
ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (อังกฤษ: shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้นๆ
นิยาม
ปัญหาวิถีสั้นสุดอาจแตกต่างกันออกไป ตามแต่ประเภทของกราฟที่กำลังจะดำเนินการ เช่น กราฟระบุทิศทาง/กราฟไม่ระบุทิศทาง/ หรือ กราฟถ่วงน้ำหนัก/ เป็นต้น วิถีสั้นสุดจากจุดยอด 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(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 | |
O(V logE/V L) | Gabow 1983b , Gabow 1985b | |
O(E + V√log L) | Ahuja et al. 1990 |
กราฟเชิงระนาบที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
กราฟสำหรับเส้นเชื่อมน้ำหนักใดๆ
กราฟเชิงระนาบสำหรับเส้นเชื่อมน้ำหนักใดๆ
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ปัญหาวิถีสั้นสุดแบบทุกคู่
กราฟสำหรับเส้นเชื่อมน้ำหนักใดๆ
- ขั้นตอนวิธีของฟลอยด์-วอร์แชล ใช้เวลา O(V3) เหมาะสำหรับกราฟหนาแน่นและนำมาใช้งานได้ง่ายมาก
- ขั้นตอนวิธีของจอห์นสัน ใช้เวลา O(V2log V + VE) เหมาะสำหรับกราฟไม่หนาแน่นซึ่งเวลาการทำงานจะดีกว่าการใช้ขั้นตอนวิธีของฟลอยด์-วอร์แชลเป็นอย่างมาก
การนำไปใช้งาน
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ปัญหาที่เกี่ยวข้อง
การมองด้วยกำหนดการเชิงเส้น
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
เนื้อหาที่เกี่ยวข้อง
- การไหลในเครือข่าย
- ต้นไม้วิถีสั้นสุด
- การค้นแบบสองทิศทาง ขั้นตอนวิธีหาวิถีสั้นสุดแบบคู่เดียว
อ้างอิง
หมายเหตุ
บรรณานุกรม
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; (April 1990). "Faster algorithms for the shortest path problem" (PDF). Journal of the ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. :1721.1/47994. S2CID 5499589. เก็บ (PDF)จากแหล่งเดิมเมื่อ 2022-10-09.
- (1958). "On a routing problem". Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. 0102435.
- Cherkassky, Boris 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. 1392160.
- ; ; ; (2001) [1990]. "Single-Source Shortest Paths and All-Pairs Shortest Paths". (2nd ed.). MIT Press and McGraw-Hill. pp. 580–642. ISBN .
- Dantzig, G. B. (January 1960). "On the Shortest Route through a Network". Management Science. 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
- (1959). "A note on two problems in connexion with graphs". Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID 123284777.
- Ford, L. R. (1956). "Network Flow Theory". Rand Corporation. P-923.
{{}}
: Cite journal ต้องการ|journal=
((help)) - ; (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th Annual Symposium on Foundations of Computer Science. IEEE. pp. 338–346. doi:10.1109/SFCS.1984.715934. ISBN .
- ; (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. S2CID 7904683.
- (1983). "Scaling algorithms for network problems". Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983) (PDF). pp. 248–258. doi:10.1109/SFCS.1983.68.
- (1985). "Scaling algorithms for network problems". . 31 (2): 148–168. doi:10.1016/0022-0000(85)90039-X. 0828519.
- Hagerup, Torben (2000). Montanari, Ugo; Rolim, José D. P.; Welzl, Emo (บ.ก.). Improved Shortest Paths on the Word RAM. Proceedings of the 27th International Colloquium on Automata, Languages and Programming. pp. 61–72. ISBN .
- Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997). "Faster Shortest-Path Algorithms for Planar Graphs". Journal of Computer and System Sciences. 55 (1): 3–23. doi:10.1006/jcss.1997.1493.
- (1977). "Efficient algorithms for shortest paths in sparse networks". . 24 (1): 1–13. doi:10.1145/321992.321993. S2CID 207678246.
- Altıntaş, Gökhan (2020). Exact Solutions of Shortest-Path Problems Based on Mechanical Analogies: In Connection with Labyrinths. Amazon Digital Services LLC. p. 97. ISBN .
- (December 1981). "A priority queue in which initialization and queue operations take O(log log D) time". Mathematical Systems Theory. 15 (1): 295–309. doi:10.1007/BF01786986. 0683047. S2CID 35703411.
- Karlsson, Rolf G.; Poblete, Patricio V. (1983). "An O(m log log D) algorithm for shortest paths". . 6 (1): 91–93. doi:10.1016/0166-218X(83)90104-X. 0700028.
- Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; 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.
- (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.
- Pettie, Seth; Ramachandran, Vijaya (2002). Computing shortest paths with comparisons and additions. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 267–276. ISBN .
- Pettie, Seth (26 January 2004). "A new approach to all-pairs shortest paths on real-weighted graphs". Theoretical Computer Science. 312 (1): 47–74. doi:10.1016/s0304-3975(03)00402-x.
- Pollack, Maurice; Wiebenson, Walter (March–April 1960). "Solution of the Shortest-Route Problem—A Review". Oper. Res. 8 (2): 224–230. doi:10.1287/opre.8.2.224. Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225.
- Schrijver, Alexander (2004). Combinatorial Optimization — Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. ISBN . Here: vol.A, sect.7.5b, p. 103
- Shimbel, Alfonso (1953). "Structural parameters of communication networks". Bulletin of Mathematical Biophysics. 15 (4): 501–507. doi:10.1007/BF02476438.
- Shimbel, A. (1955). Structure in communication nets. Proceedings of the Symposium on Information Networks. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn. pp. 199–203.
- Thorup, Mikkel (1999). "Undirected single-source shortest paths with positive integer weights in linear time". Journal of the ACM. 46 (3): 362–394. doi:10.1145/316542.316548. S2CID 207654795.
- Thorup, Mikkel (2004). "Integer priority queues with decrease key in constant time and the single source shortest paths problem". Journal of Computer and System Sciences. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003.
- Whiting, P. D.; Hillier, J. A. (March–June 1960). "A Method for Finding the Shortest Route through a Road Network". Operational Research Quarterly. 11 (1/2): 37–40. doi:10.1057/jors.1960.32.
- (2014). "Faster all-pairs shortest paths via circuit complexity". . New York: ACM. pp. 664–673. :1312.6680. doi:10.1145/2591796.2591811. 3238994.
อ่านเพิ่ม
- 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. 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.
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir inthvsdikraf pyhawithisnsud xngkvs shortest path problem epnpyhathitxngkarhawithisnsudrahwangcudyxd 2 cudphayinkraf klawkhuxinwithisnsudnn phlrwmkhxngnahnkinesnechuxmaetlaesnrwmknaelwnxythisudinbrrdawithithnghmd twxyangpyhaniechnkarhawithiedinthangcakcudhnungipxikcudhnunginaephnthi inkrnini cudyxdaethndwysthanthitang swnesnechuxmaethndwythnnhruxesnthang aelanahnkbnesnechuxmaethndwyewlainkaredinthangdwythnnhruxesnthangnnwithisnsudbnkrafimrabuthisthangthiimthwngnahnkrahwangcudyxd 6 kb 1 khux 6 4 5 1 niyampyhawithisnsudxacaetktangknxxkip tamaetpraephthkhxngkrafthikalngcadaeninkar echn krafrabuthisthang krafimrabuthisthang hrux krafthwngnahnk epntn withisnsudcakcudyxd u ip v khuxwithithimicuderimtnthi u aelacbthi v odythiphlrwmkhxngnahnkinwithinnnxythisudinbrrdawithithnghmdcak u ip v sahrbkrafimthwngnahnk niyamihwithisnsudkhuxwithithimiesnechuxmnxythisud odythwip pyhawithisnsudcakahndcudyxd u aela v maihaelaihhawithisnsudrahwangcudyxdthngkhu eriykpyhaniwapyhawithisnsudaebbkhuediyw nxkcakniyngmipyhawithisnsudxyudwyknxik 3 rupaebb khux pyhawithisnsudaebbaehlngtnthangediyw epnpyhathitxngkarhawithisnsudcakcudyxd v ipcudyxdxunthnghmdinkraf pyhawithisnsudaebbaehlngplaythangediyw epnpyhathitxngkarhawithisnsudcakcudyxdthnghmdmathicudyxd v pyhaniinkrnikhxngkrafimrabuthisthangsamarthaekidthnthiodymxngplaythangepntnthang aelwaekikhpyhawithisnsudaebbaehlngtnthangediywaethn inkrnikrafrabuthisthangksamarthldruppyhamaepnpyhawithisnsudaebbaehlngtnthangediywidechnkn odyklbesnechuxmcakcudyxd a ip b epn b ip a kxn aelwaekikhpyhawithisnsudaebbaehlngtnthangediywcak v aethn pyhawithisnsudaebbthukkhu epnpyhathitxngkarhawithisnsudcak u ip v sahrbthukcudyxd u v phayinkraf sngektwapyhaaetlarupaebbsamarthaekidodykaraekpyhawithisnsudaebbkhuediywhlaykhrng xyangirktam karaekikhpyhainaetlarupaebbmiwithikarthiaetktangknxxkipsungthaihmiprasiththiphaphmakkwakaraekpyhapyhawithisnsudaebbkhuediywhlaykhrng xnthicring n pccubn yngimmikhntxnwithiidthikrnielwraysudsamarthaekpyhawithisnsudaebbkhuediywodythimiprasiththiphaphdanewlamakkwapyhawithisnsudaebbaehlngtnthangediywid dngnnemuxtxngkaraekpyhawithisnsudaebbkhuediyw odythwipkcaaekpyhawithisnsudaebbaehlngtnthangediywcnidkhatxbthitxngkaraelacbkhntxnwithi xyangirktam sahrbkrafphiessbangpraephthsamarthaekpyhawithisnsudaebbkhuediywodyid echn kraftnim epntn txngkarxangxing khntxnwithikhntxnwithiinkaraekpyhawithisnsud caichaenwkhidkhxngkarkarkhlayesnechuxm relaxation nnkhuxkhnaerimtn khatxbwithisnsudcayngimthuktxng esnechuxm e caeriykwa tung tense thasamarthich e aelwthaihmiwithithinahnkrwmrxykwakhatxbthimixyu dngnnkhntxnwithiaekpyhawithisnsudkcathakarkhlayesnechuxmthitung nnkhuxichesnechuxmthitungephuxihidkhatxbkhxngwithisnsudthidiyingkhuneruxy sudthayemuximphbesnechuxmthitungkaeplwawithithiidepnwithisnsudaelw pyhawithisnsudmxngaetephiyngkaripthungidkhxngcudyxdtangethann dngnnsahrbkrafimrabuthisthangcungsamarthaeplngepnkrafrabuthisthangid odykarepliynesnechuxmimmithisthang epnesnechuxmmithisthang 2 esnthimithisthngipaelaklb sahrbkrafimthwngnahnk cakniyamthikahndihwithisnsudkhuxmicanwnesnechuxminwithinxythisud dngnncungxacklawidwaesnechuxmthukesnmikhwamsakhyethakn klawkhuxkrafimthwngnahnkcaethiybethakbkrafthwngnahnkthiesnechuxmthukesnminahnkethaknaelaimepnlb twxyangechnkrafthwngnahnkhnunghnwy unit weight graph epntn khntxnwithiinkaraekpyhathiidrbkhwamniymaelasakhymidngni khntxnwithikhxngidkhstra ichaekpyhawithisnsudaebbaehlngtnthangediyw odythinahnkkhxngesnechuxmtxngimepnlb khntxnwithikhxngeblaemn fxrd ichaekpyhawithisnsudaebbaehlngtnthangediyw odythinahnkkhxngesnechuxmxacepnlbid khntxnwithiexstar ichaekpyhawithisnsudaebbaehlngtnthangediyw odyichsuksasanukephuxephimkhwamerwinkaraekpyha khntxnwithikhxngflxyd wxraechl ichaekpyhawithisnsudaebbthukkhu khntxnwithikhxngcxhnsn ichaekpyhawithisnsudaebbthukkhu sungcaerwkwakhntxnwithikhxngflxyd wxraechlinkrnikhxngkrafimhnaaenn khntxnwithixunaelakarnamaichnganinrupaebbtangxachaidthi Cherkassky et al pyhawithisnsudaebbaehlngtnthangediyw pyhawithisnsudaebbaehlngtnthangediywepnpyhathitxngkarhawithisnsudcakcudyxd v ipcudyxdxunthnghmdinkraf idtnimwithisnsudxxkmaepnphllphth krafthwngnahnkhnunghnwy thakarkhntamaenwkwang ichewla O V E sahrbesnechuxmnahnkid thaaelakahndkarphlwt ichewla O V E krafthiimmiesnechuxmnahnktidlb khntxnwithi khwamsbsxnthangdanewla phukhidkhnO V4 Shimbel 1955O V2EL Ford 1956khntxnwithikhxngeblaemn fxrd O VE Bellman 1958 Moore 1959O V2 log V Dantzig 1958harvnb error no target CITEREFDantzig1958 Dantzig 1960 Minty cf Pollack amp Wiebenson 1960 Whiting amp Hillier 1960khntxnwithikhxngidkhstra O V2 Leyzorek et al 1957 Dijkstra 1959 khntxnwithikhxngidkhstraphrxmichhipfiobnchchi O E V log V Fredman amp Tarjan 1984 Fredman amp Tarjan 1987O E log log L Johnson 1982harvnb error no target CITEREFJohnson1982 Karlsson amp Poblete 1983O V logE V L Gabow 1983bharvnb error no target CITEREFGabow1983b Gabow 1985bharvnb error no target CITEREFGabow1985b O E V log L Ahuja et al 1990krafechingranabthiimmiesnechuxmnahnktidlb swnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidkrafsahrbesnechuxmnahnkid khntxnwithikhxngeblaemn fxrdkrafechingranabsahrbesnechuxmnahnkid swnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidpyhawithisnsudaebbthukkhu krafsahrbesnechuxmnahnkid khntxnwithikhxngflxyd wxraechl ichewla O V3 ehmaasahrbkrafhnaaennaelanamaichnganidngaymak khntxnwithikhxngcxhnsn ichewla O V2log V VE ehmaasahrbkrafimhnaaennsungewlakarthangancadikwakarichkhntxnwithikhxngflxyd wxraechlepnxyangmakkarnaipichnganswnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidpyhathiekiywkhxngkarmxngdwykahndkarechingesnswnnirxephimetimkhxmul khunsamarthchwyephimkhxmulswnniidenuxhathiekiywkhxngkarihlinekhruxkhay tnimwithisnsud karkhnaebbsxngthisthang khntxnwithihawithisnsudaebbkhuediywxangxinghmayehtu http www boost org libs graph doc graph theory review html sec shortest paths algorithms http www cp eng chula ac th somchai ULearn Algorithms index htm ody smchay prasiththicutrakul Cherkassky Goldberg amp Radzik 1996 http xlinux nist gov dads HTML dagShortPath html brrnanukrm Ahuja Ravindra K Mehlhorn Kurt Orlin James April 1990 Faster algorithms for the shortest path problem PDF Journal of the ACM ACM 37 2 213 223 doi 10 1145 77600 77615 1721 1 47994 S2CID 5499589 ekb PDF cakaehlngedimemux 2022 10 09 1958 On a routing problem Quarterly of Applied Mathematics 16 87 90 doi 10 1090 qam 102435 0102435 Cherkassky Boris 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 1392160 2001 1990 Single Source Shortest Paths and All Pairs Shortest Paths 2nd ed MIT Press and McGraw Hill pp 580 642 ISBN 0 262 03293 7 Dantzig G B January 1960 On the Shortest Route through a Network Management Science 6 2 187 190 doi 10 1287 mnsc 6 2 187 1959 A note on two problems in connexion with graphs Numerische Mathematik 1 269 271 doi 10 1007 BF01386390 S2CID 123284777 Ford L R 1956 Network Flow Theory Rand Corporation P 923 a href wiki E0 B9 81 E0 B8 A1 E0 B9 88 E0 B9 81 E0 B8 9A E0 B8 9A Cite journal title aemaebb Cite journal cite journal a Cite journal txngkar journal help 1984 Fibonacci heaps and their uses in improved network optimization algorithms 25th Annual Symposium on Foundations of Computer Science IEEE pp 338 346 doi 10 1109 SFCS 1984 715934 ISBN 0 8186 0591 X 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 S2CID 7904683 1983 Scaling algorithms for network problems Proceedings of the 24th Annual Symposium on Foundations of Computer Science FOCS 1983 PDF pp 248 258 doi 10 1109 SFCS 1983 68 1985 Scaling algorithms for network problems 31 2 148 168 doi 10 1016 0022 0000 85 90039 X 0828519 Hagerup Torben 2000 Montanari Ugo Rolim Jose D P Welzl Emo b k Improved Shortest Paths on the Word RAM Proceedings of the 27th International Colloquium on Automata Languages and Programming pp 61 72 ISBN 978 3 540 67715 4 Henzinger Monika R Klein Philip Rao Satish Subramanian Sairam 1997 Faster Shortest Path Algorithms for Planar Graphs Journal of Computer and System Sciences 55 1 3 23 doi 10 1006 jcss 1997 1493 1977 Efficient algorithms for shortest paths in sparse networks 24 1 1 13 doi 10 1145 321992 321993 S2CID 207678246 Altintas Gokhan 2020 Exact Solutions of Shortest Path Problems Based on Mechanical Analogies In Connection with Labyrinths Amazon Digital Services LLC p 97 ISBN 9798655831896 December 1981 A priority queue in which initialization and queue operations take O log log D time Mathematical Systems Theory 15 1 295 309 doi 10 1007 BF01786986 0683047 S2CID 35703411 Karlsson Rolf G Poblete Patricio V 1983 An O m log log D algorithm for shortest paths 6 1 91 93 doi 10 1016 0166 218X 83 90104 X 0700028 Leyzorek M Gray R S Johnson A A Ladew W C Meaker S R Jr 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 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 Pettie Seth Ramachandran Vijaya 2002 Computing shortest paths with comparisons and additions Proceedings of the Thirteenth Annual ACM SIAM Symposium on Discrete Algorithms pp 267 276 ISBN 978 0 89871 513 2 Pettie Seth 26 January 2004 A new approach to all pairs shortest paths on real weighted graphs Theoretical Computer Science 312 1 47 74 doi 10 1016 s0304 3975 03 00402 x Pollack Maurice Wiebenson Walter March April 1960 Solution of the Shortest Route Problem A Review Oper Res 8 2 224 230 doi 10 1287 opre 8 2 224 Attributes Dijkstra s algorithm to Minty private communication on p 225 Schrijver Alexander 2004 Combinatorial Optimization Polyhedra and Efficiency Algorithms and Combinatorics Vol 24 Springer ISBN 978 3 540 20456 5 Here vol A sect 7 5b p 103 Shimbel Alfonso 1953 Structural parameters of communication networks Bulletin of Mathematical Biophysics 15 4 501 507 doi 10 1007 BF02476438 Shimbel A 1955 Structure in communication nets Proceedings of the Symposium on Information Networks New York NY Polytechnic Press of the Polytechnic Institute of Brooklyn pp 199 203 Thorup Mikkel 1999 Undirected single source shortest paths with positive integer weights in linear time Journal of the ACM 46 3 362 394 doi 10 1145 316542 316548 S2CID 207654795 Thorup Mikkel 2004 Integer priority queues with decrease key in constant time and the single source shortest paths problem Journal of Computer and System Sciences 69 3 330 353 doi 10 1016 j jcss 2004 04 003 Whiting P D Hillier J A March June 1960 A Method for Finding the Shortest Route through a Road Network Operational Research Quarterly 11 1 2 37 40 doi 10 1057 jors 1960 32 2014 Faster all pairs shortest paths via circuit complexity New York ACM pp 664 673 1312 6680 doi 10 1145 2591796 2591811 3238994 xanephimFrigioni 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 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 cakaehlngedimemux November 17 2015 DTIC AD 661265