ผลต่างระหว่างรุ่นของ "ปัญหาวิถีสั้นสุด"
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.1 |
|||
บรรทัด 112: | บรรทัด 112: | ||
== อ้างอิง == |
== อ้างอิง == |
||
=== หมายเหตุ === |
|||
{{รายการอ้างอิง}} |
{{รายการอ้างอิง}} |
||
⚫ | |||
=== บรรณานุกรม === |
|||
*{{cite conference |url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.9856 |title=Fully dynamic output bounded single source shortest path problem |author=D. Frigioni |coauthors=A. Marchetti-Spaccamela and U. Nanni |year=1998 |booktitle=Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms |pages=212-221 |location=Atlanta, GA |doi= }} |
|||
{{refbegin}} |
|||
*{{cite journal |last2=Mehlhorn |first2=Kurt |last3=Orlin |first3=James |last4=Tarjan |first4=Robert E. |date=April 1990 |title=Faster algorithms for the shortest path problem |url=https://apps.dtic.mil/sti/pdfs/ADA194031.pdf |journal=Journal of the ACM |publisher=ACM |volume=37 |issue=2 |pages=213–223 |last1=Ahuja |first1=Ravindra K. |author4-link=Robert Tarjan |doi=10.1145/77600.77615|hdl=1721.1/47994 |s2cid=5499589 |hdl-access=free }} |
|||
* {{cite journal |last=Bellman |first=Richard |year=1958 |title=On a routing problem |journal=Quarterly of Applied Mathematics |volume=16 |pages=87–90 |mr=0102435 |author-link=Richard Bellman |doi=10.1090/qam/102435|doi-access=free }} |
|||
*{{Cite journal |last2=Goldberg |first2=Andrew V. |last3=Radzik |first3=Tomasz |year=1996 |title=Shortest paths algorithms: theory and experimental evaluation |url=http://ftp.cs.stanford.edu/cs/theory/pub/goldberg/sp-alg.ps.Z |journal=Mathematical Programming |series=Ser. A |volume=73 |issue=2 |pages=129–174 |doi=10.1016/0025-5610(95)00021-6 |mr=1392160 |last1=Cherkassky |first1=Boris V. |author2-link=Andrew V. Goldberg }} |
|||
⚫ | |||
*{{cite journal |last=Dantzig |first=G. B. |date=January 1960 |title=On the Shortest Route through a Network |journal=Management Science |volume=6 |issue=2 |pages=187–190 |doi=10.1287/mnsc.6.2.187}} |
|||
* {{cite journal |year=1959 |title=A note on two problems in connexion with graphs |journal=Numerische Mathematik |volume=1 |pages=269–271 |doi=10.1007/BF01386390|last1=Dijkstra |first1=E. W. |s2cid=123284777 |author-link=Edsger W. Dijkstra }} |
|||
* {{cite journal |last=Ford |first=L. R. |title=Network Flow Theory |publisher=Rand Corporation |id=P-923 |date=1956 |url=http://www.rand.org/pubs/papers/P923.html}}<!--cited in Dijkstra 1959--> |
|||
* {{cite conference |last1=Fredman |first1=Michael Lawrence |author-link1=Michael Fredman |first2=Robert E. |last2=Tarjan |author-link2=Robert Tarjan |title=Fibonacci heaps and their uses in improved network optimization algorithms |conference=25th Annual Symposium on Foundations of Computer Science |year=1984 |publisher=[[IEEE]] |pages=338–346|doi=10.1109/SFCS.1984.715934 |isbn=0-8186-0591-X}} |
|||
* {{cite journal |last2=Tarjan |first2=Robert E. |year=1987 |title=Fibonacci heaps and their uses in improved network optimization algorithms |journal=Journal of the Association for Computing Machinery |volume=34 |issue=3 |pages=596–615 |doi=10.1145/28869.28874 |last1=Fredman |first1=Michael Lawrence |s2cid=7904683 |author-link1=Michael Fredman |author-link2=Robert Tarjan }} |
|||
* {{cite conference |
|||
| last = Gabow | first = H. N. | author-link = Harold N. Gabow |
|||
| contribution = Scaling algorithms for network problems |
|||
| doi = 10.1109/SFCS.1983.68 |
|||
| pages = 248–258 |
|||
| title = Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS 1983) |
|||
| year = 1983 |
|||
| url = http://www.eecs.umich.edu/%7Epettie/matching/Gabow-scaling-algorithms-for-network-problems.pdf |
|||
}} |
|||
*{{cite journal |
|||
| last = Gabow | first = Harold N. | author-link = Harold N. Gabow |
|||
| year = 1985 |
|||
| title = Scaling algorithms for network problems |
|||
| journal = [[Journal of Computer and System Sciences]] |
|||
| volume = 31 |
|||
| issue = 2 |
|||
| pages = 148–168 |
|||
| doi = 10.1016/0022-0000(85)90039-X |
|||
| mr = 828519 |
|||
| doi-access = free |
|||
}} |
|||
*{{cite book |url=http://dl.acm.org/citation.cfm?id=686343&CFID=563073233&CFTOKEN=28801665 |title=Improved Shortest Paths on the Word RAM |first=Torben |year=2000 |isbn=978-3-540-67715-4 |pages=61–72 |last1=Hagerup |journal=Proceedings of the 27th International Colloquium on Automata, Languages and Programming |editor1-first=Ugo |editor1-last=Montanari |editor2-first=José D. P. |editor2-last=Rolim |editor3-first=Emo |editor3-last=Welzl }} |
|||
*{{cite journal |
|||
| last = Johnson |
|||
| first = Donald B. |
|||
| author-link = Donald B. Johnson |
|||
| title = Efficient algorithms for shortest paths in sparse networks |
|||
| journal = [[Journal of the ACM]] |
|||
| volume = 24 |
|||
| issue = 1 |
|||
| pages = 1–13 |
|||
| year = 1977 |
|||
| doi=10.1145/321992.321993| s2cid = 207678246 |
|||
}} |
|||
*{{cite book |
|||
|last=Altıntaş |
|||
|first=Gökhan |
|||
|date=2020 |
|||
|title= Exact Solutions of Shortest-Path Problems Based on Mechanical Analogies: In Connection with Labyrinths |
|||
|url=https://books.google.com/books?id=oSvHzQEACAAJ |
|||
|publisher= Amazon Digital Services LLC |
|||
|page= 97 |
|||
|isbn= 9798655831896 |
|||
}} |
|||
*{{cite journal |
|||
| last = Johnson | first = Donald B. | date = December 1981 |
|||
| title = A priority queue in which initialization and queue operations take {{math|''O''(log log ''D'')}} time |
|||
| journal = Mathematical Systems Theory |
|||
| volume = 15 |
|||
| issue = 1 |
|||
| pages = 295–309 |
|||
| doi = 10.1007/BF01786986 |
|||
| mr = 683047 |
|||
| s2cid = 35703411 | author-link = Donald B. Johnson |
|||
}} |
|||
*{{cite journal |
|||
| last2 = Poblete | first2 = Patricio V. |
|||
| year = 1983 |
|||
| title = An {{math|''O''(''m'' log log ''D'')}} algorithm for shortest paths |
|||
| journal = [[Discrete Applied Mathematics]] |
|||
| volume = 6 |
|||
| issue = 1 |
|||
| pages = 91–93 |
|||
| doi = 10.1016/0166-218X(83)90104-X |
|||
| mr = 700028 |
|||
| last1 = Karlsson | first1 = Rolf G. |
|||
| doi-access = free |
|||
}} |
|||
* {{cite book |title=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems |last2=Gray |first2=R. S. |last3=Johnson |first3=A. A. |last4=Ladew |first4=W. C. |last5=Meaker |first5=S. R., Jr. |last6=Petry |first6=R. M. |last7=Seitz |first7=R. N. |publisher=Case Institute of Technology |year=1957 |location=Cleveland, Ohio |last1=Leyzorek |first1=M.}} |
|||
* {{cite conference |last=Moore |first= E. F. |author-link=Edward F. Moore |year=1959 |title=The shortest path through a maze |pages=285–292 |book-title=Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957) |publisher=Harvard University Press |location=Cambridge }} |
|||
*{{cite book |url=https://archive.org/details/proceedingsofthi2002acms/page/267 |title=Computing shortest paths with comparisons and additions |last2=Ramachandran |first2=Vijaya |year=2002 |isbn=978-0-89871-513-2 |pages=[https://archive.org/details/proceedingsofthi2002acms/page/267 267–276] |last1=Pettie |first1=Seth |journal=Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms }} |
|||
*{{cite journal |last=Pettie |first=Seth |date=26 January 2004 |title=A new approach to all-pairs shortest paths on real-weighted graphs |journal=Theoretical Computer Science |volume=312 |issue=1 |pages=47–74 |doi=10.1016/s0304-3975(03)00402-x|doi-access=free }} |
|||
*{{cite journal | last1=Pollack |first1= Maurice |last2=Wiebenson |first2=Walter |date=March–April 1960 |title=Solution of the Shortest-Route Problem—A Review |journal=Oper. Res. |volume=8 |issue=2 |pages=224–230 |doi=10.1287/opre.8.2.224}} Attributes Dijkstra's algorithm to Minty ("private communication") on p. 225. |
|||
* {{cite book| title=Combinatorial Optimization — Polyhedra and Efficiency|last=Schrijver|first=Alexander | publisher=Springer| year=2004| isbn=978-3-540-20456-5 | series=Algorithms and Combinatorics| volume=24}} Here: vol.A, sect.7.5b, p. 103 |
|||
* {{cite journal|last=Shimbel|first=Alfonso|year=1953|title=Structural parameters of communication networks|journal=Bulletin of Mathematical Biophysics|volume=15|issue=4|pages=501–507|doi=10.1007/BF02476438 }} |
|||
* {{cite conference|last=Shimbel|first=A.|title=Structure in communication nets|location=New York, NY|pages=199–203|publisher=Polytechnic Press of the Polytechnic Institute of Brooklyn|conference=Proceedings of the Symposium on Information Networks|year=1955}} |
|||
*{{cite journal|date=1999|title=Undirected single-source shortest paths with positive integer weights in linear time|journal=Journal of the ACM|volume=46|issue=3|pages=362–394|last1=Thorup|first1=Mikkel|doi=10.1145/316542.316548|s2cid=207654795}} |
|||
*{{Cite journal|last=Thorup|first=Mikkel|date=2004|title=Integer priority queues with decrease key in constant time and the single source shortest paths problem|url=http://dl.acm.org/citation.cfm?id=1039326|journal=Journal of Computer and System Sciences|volume=69|issue=3|pages=330–353|doi=10.1016/j.jcss.2004.04.003|doi-access=free}} |
|||
*{{cite journal |last2=Hillier |first2=J. A. |date=March–June 1960 |title=A Method for Finding the Shortest Route through a Road Network |journal=Operational Research Quarterly |volume=11 |issue=1/2 |pages=37–40 |last1=Whiting |first1=P. D. |doi=10.1057/jors.1960.32}} |
|||
*{{cite conference |last=Williams |first=Ryan |author-link=Ryan Williams (computer scientist) |arxiv=1312.6680 |contribution=Faster all-pairs shortest paths via circuit complexity |doi=10.1145/2591796.2591811 |mr=3238994 |pages=664–673 |publisher=ACM |location=New York |title=Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14) |year=2014 |title-link=Symposium on Theory of Computing }} |
|||
{{refend}} |
|||
== ดูเพิ่ม == |
== ดูเพิ่ม == |
รุ่นแก้ไขเมื่อ 23:10, 17 สิงหาคม 2565
บทความนี้ไม่มีการอ้างอิงจากแหล่งที่มาใด |
ในทฤษฎีกราฟ ปัญหาวิถีสั้นสุด (อังกฤษ: shortest path problem) เป็นปัญหาที่ต้องการหาวิถีสั้นสุดระหว่างจุดยอด 2 จุดภายในกราฟ กล่าวคือในวิถีสั้นสุดนั้น ผลรวมของน้ำหนักในเส้นเชื่อมแต่ละเส้นรวมกันแล้วน้อยที่สุดในบรรดาวิถีทั้งหมด ตัวอย่างปัญหานี้เช่นการหาวิธีเดินทางจากจุดหนึ่งไปอีกจุดหนึ่งในแผนที่ ในกรณีนี้ จุดยอดแทนด้วยสถานที่ต่างๆ ส่วนเส้นเชื่อมแทนด้วยถนนหรือเส้นทาง และน้ำหนักบนเส้นเชื่อมแทนด้วยเวลาในการเดินทางด้วยถนนหรือเส้นทางนั้นๆ
นิยาม
ปัญหาวิถีสั้นสุดอาจแตกต่างกันออกไป ตามแต่ประเภทของกราฟที่กำลังจะดำเนินการ เช่น กราฟระบุทิศทาง/กราฟไม่ระบุทิศทาง/กราฟผสม หรือ กราฟถ่วงน้ำหนัก/กราฟไม่ถ่วงน้ำหนัก เป็นต้น วิถีสั้นสุดจากจุดยอด 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(V + E)[2]
กราฟอวัฏจักรระบุทิศทางสำหรับเส้นเชื่อมน้ำหนักใดๆ
- ทำการเรียงเชิงทอพอโลยีและกำหนดการพลวัต ใช้เวลา O(V + E)[4]
กราฟที่ไม่มีเส้นเชื่อมน้ำหนักติดลบ
ขั้นตอนวิธี | ความซับซ้อนทางด้านเวลา | ผู้คิดค้น |
---|---|---|
O(V4) | Shimbel 1955 | |
O(V2EL) | Ford 1956 | |
ขั้นตอนวิธีของเบลแมน-ฟอร์ด | O(VE) | Bellman 1958, Moore 1959 harvnb error: multiple targets (2×): CITEREFMoore1959 (help) |
O(V2 log V) | Dantzig 1958 , Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960 | |
ขั้นตอนวิธีของไดค์สตรา | O(V2) | Leyzorek et al. 1957 harvnb error: multiple targets (2×): CITEREFLeyzorekGrayJohnsonLadew1957 (help), Dijkstra 1959 harvnb error: multiple targets (2×): CITEREFDijkstra1959 (help) |
... | ... | ... |
ขั้นตอนวิธีของไดค์สตราพร้อมใช้ฮีปฟีโบนัชชี | O(E + V log V) | Fredman & Tarjan 1984 harvnb error: multiple targets (2×): CITEREFFredmanTarjan1984 (help), Fredman & Tarjan 1987 harvnb error: multiple targets (2×): CITEREFFredmanTarjan1987 (help) |
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) เหมาะสำหรับกราฟไม่หนาแน่นซึ่งเวลาการทำงานจะดีกว่าการใช้ขั้นตอนวิธีของฟลอยด์-วอร์แชลเป็นอย่างมาก
การนำไปใช้งาน
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
ปัญหาที่เกี่ยวข้อง
การมองด้วยกำหนดการเชิงเส้น
ส่วนนี้รอเพิ่มเติมข้อมูล คุณสามารถช่วยเพิ่มข้อมูลส่วนนี้ได้ |
เนื้อหาที่เกี่ยวข้อง
- การไหลในเครือข่าย
- ต้นไม้วิถีสั้นสุด
- ปัญหาวิถีสั้นสุดบนระนาบแบบยุคลิด
- การค้นแบบสองทิศทาง ขั้นตอนวิธีหาวิถีสั้นสุดแบบคู่เดียว
อ้างอิง
หมายเหตุ
- ↑ http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:shortest-paths-algorithms
- ↑ 2.0 2.1 2.2 http://www.cp.eng.chula.ac.th/~somchai/ULearn/Algorithms/index.htm โดย สมชาย ประสิทธิ์จูตระกูล
- ↑ 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.
{{cite journal}}
:|ref=harv
ไม่ถูกต้อง (help) - ↑ http://xlinux.nist.gov/dads/HTML/dagShortPath.html
บรรณานุกรม
- Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). "Faster algorithms for the shortest path problem" (PDF). Journal of the ACM. ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589.
- Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics. 16: 87–90. doi:10.1090/qam/102435. MR 0102435.
- 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.
- 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.
- 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.
- Dijkstra, E. W. (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}}
: Cite journal ต้องการ|journal=
(help) - 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. pp. 338–346. doi:10.1109/SFCS.1984.715934. ISBN 0-8186-0591-X.
- 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. S2CID 7904683.
- Gabow, H. N. (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.
- Gabow, Harold N. (1985). "Scaling algorithms for network problems". Journal of Computer and System Sciences. 31 (2): 148–168. doi:10.1016/0022-0000(85)90039-X. MR 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 978-3-540-67715-4.
- Johnson, Donald B. (1977). "Efficient algorithms for shortest paths in sparse networks". Journal of the ACM. 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 9798655831896.
- Johnson, Donald B. (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. MR 0683047. S2CID 35703411.
- Karlsson, Rolf G.; Poblete, Patricio V. (1983). "An O(m log log D) algorithm for shortest paths". Discrete Applied Mathematics. 6 (1): 91–93. doi:10.1016/0166-218X(83)90104-X. MR 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.
- 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.
- 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.
- Williams, Ryan (2014). "Faster all-pairs shortest paths via circuit complexity". Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC '14). New York: ACM. pp. 664–673. arXiv:1312.6680. doi:10.1145/2591796.2591811. MR 3238994.
ดูเพิ่ม
- Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.
{{cite journal}}
:|ref=harv
ไม่ถูกต้อง (help) - 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2012-10-11. สืบค้นเมื่อ 2011-11-20.
{{cite journal}}
:|ref=harv
ไม่ถูกต้อง (help) - 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.
{{cite journal}}
:|ref=harv
ไม่ถูกต้อง (help) - 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.
{{cite book}}
:|ref=harv
ไม่ถูกต้อง (help) - 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.
{{cite conference}}
:|ref=harv
ไม่ถูกต้อง (help); ไม่รู้จักพารามิเตอร์|booktitle=
ถูกละเว้น แนะนำ (|book-title=
) (help)