ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของไดก์สตรา"

ขั้นตอนวิธีของไดก์สตรา
	รูปภาพแสดงขั้นตอนวิธีของไดก์สตรา
ประเภท	ขั้นตอนวิธีการค้นหา
โครงสร้างข้อมูล	กราฟ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด
	ด; ค; ก;

เรียกดูประวัติแบบโต้ตอบ

← การแก้ไขก่อนหน้า การแก้ไขถัดไป →

เนื้อหาที่ลบ เนื้อหาที่เพิ่ม

เห็นภาพข้อความวิกิ

ในบรรทัด

รุ่นแก้ไขเมื่อ 16:44, 5 พฤศจิกายน 2565

ขั้นตอนวิธีของไดก์สตรา (อังกฤษ: Dijkstra's algorithm) ถูกคิดค้นขึ้นโดยนักวิทยาการคอมพิวเตอร์ชาวดัตช์นามว่า แอ็ดส์เคอร์ ไดก์สตรา (Edsger Dijkstra) ในปี 1959 เพื่อแก้ไขปัญหาวิถีสั้นสุดจากจุดหนึ่งใด ๆ สำหรับกราฟที่มีความยาวของเส้นเชื่อมไม่เป็นลบ สำหรับขั้นตอนวิธีนี้จะหาระยะทางสั้นที่สุดจากจุดหนึ่งไปยังจุดใด ๆ ในกราฟโดยจะหาเส้นทางที่สั้นที่สุดไปทีละจุดยอดเรื่อย ๆ จนครบตามที่ต้องการ

ขั้นตอนวิธี

กำหนดให้ปมหนึ่งเป็นปมเริ่มต้น (initial node) และกำหนดให้ "ระยะทางของปม Y" (distance of node Y) หมายถึงระยะทางจากปมเริ่มต้นไปยังปม Y ขั้นตอนวิธีของไดก์สตราจะกำหนดค่าระยะทางเริ่มต้นไว้บางปมและจะเพิ่มค่าไปทีละขั้นตอน

กำหนดให้ทุกปมมีค่าระยะทางตามเส้นเชื่อม โดยให้ปมเริ่มต้นมีค่าเป็นศูนย์ และปมอื่นมีค่าเป็นอนันต์
ทำเครื่องหมายทุกปมยกเว้นปมเริ่มต้นว่ายังไม่ไปเยือน (unvisited) ตั้งให้ปมเริ่มต้นเป็นปมปัจจุบัน สร้างเซตของปมที่ยังไม่ไปเยือนขึ้นมาเซตหนึ่งซึ่งประกอบด้วยทุกปมยกเว้นปมเริ่มต้น
จากปมปัจจุบัน พิจารณาปมข้างเคียงตามเส้นเชื่อมทุกปมที่ยังไม่ไปเยือน และคำนวณระยะทางต่อเนื่องของเส้นเชื่อม ตัวอย่างเช่น ถ้าปมปัจจุบันคือ A มีระยะทางของปมเป็น 6 และเส้นเชื่อมที่ต่อจาก A ไปยังปมข้างเคียง B มีระยะทางเป็น 2 ดังนั้นระยะทางของปม B (โดยผ่าน A) จึงเท่ากับ 6+2=8 เป็นต้น ถ้าระยะทางที่คำนวณได้มีค่าน้อยกว่าค่าระยะทางที่บันทึกอยู่ของปมนั้น ให้เขียนทับค่าระยะทางของปมดังกล่าว แม้ว่าปมข้างเคียงได้ถูกพิจารณาแล้ว แต่ก็ยังไม่ทำเครื่องหมายว่าไปเยือนแล้ว (visited) ในขั้นตอนนี้ ปมข้างเคียงจะยังคงอยู่ในเซตของปมที่ยังไม่ไปเยือนเช่นเดิม
เมื่อพิจารณาปมข้างเคียงจากปมปัจจุบันครบทุกปมแล้ว ทำเครื่องหมายปมปัจจุบันว่าไปเยือนแล้ว และนำออกจากเซตของปมที่ยังไม่ไปเยือน ปมที่ไปเยือนแล้วนี้จะไม่ถูกนำมาตรวจสอบอีก ค่าระยะทางที่บันทึกอยู่จะสิ้นสุดและมีค่าน้อยสุด
ปมปัจจุบันตัวถัดไปที่ถูกเลือกจะเป็นปมที่มีค่าระยะทางน้อยสุดในเซตของปมที่ยังไม่ไปเยือน
ถ้าเซตของปมที่ยังไม่ไปเยือนฟว่างแล้วให้หยุดการทำงาน ขั้นตอนวิธีเสร็จสิ้น หากไม่ใช่ให้เลือกปมยังไม่ไปเยือนที่มีค่าระยะทางน้อยสุดเป็นปมปัจจุบัน แล้ววนกลับไปทำขั้นตอนที่ 3

การประยุกต์ใช้งาน

เราสามารถย่อส่วนปัญหาในชีวิตจริงให้เป็นปัญหาทางคณิตศาสตร์ได้ เช่น การให้จุดยอดเป็นเมืองและเส้นเชื่อมเป็นถนน

ดูเพิ่ม

ขั้นตอนวิธีของเบลแมน-ฟอร์ด สำหรับปัญหาวิถีสั้นสุดที่น้ำหนักของเส้นเชื่อมติดลบได้
ปัญหาการเดินทางของพนักงานขาย

อ้างอิง

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601. ISBN 0-262-03293-7.
Dial, Robert B. (1969). "Algorithm 360: Shortest-path forest with topological ordering [H]". Communications of the ACM. 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
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.
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.
Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65. S2CID 14986297.
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.
Knuth, D.E. (1977). "A Generalization of Dijkstra's Algorithm". Information Processing Letters. 6 (1): 1–5. doi:10.1016/0020-0190(77)90002-3.
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E. (April 1990). "Faster Algorithms for the Shortest Path Problem" (PDF). Journal of the ACM. 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. S2CID 5499589.
Raman, Rajeev (1997). "Recent results on the single-source shortest paths problem". SIGACT News. 28 (2): 81–87. doi:10.1145/261342.261352. S2CID 18031586.
Thorup, Mikkel (2000). "On RAM priority Queues". SIAM Journal on Computing. 30 (1): 86–109. doi:10.1137/S0097539795288246. S2CID 5221089.
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.

แหล่งข้อมูลอื่น

ขั้นตอนวิธีของไดก์สตราในยูทูบ

บทความนี้ยังเป็นโครง คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล

หมายเหตุ: ขอแนะนำให้จัดหมวดหมู่โครงให้เข้ากับเนื้อหาของบทความ (ดูเพิ่มที่ วิกิพีเดีย:โครงการจัดหมวดหมู่โครงที่ยังไม่สมบูรณ์)

@@ บรรทัด 30: / บรรทัด 30: @@
 == อ้างอิง ==
+* {{cite book | author1-link = Thomas H. Cormen | first1 = Thomas H. | last1 = Cormen | author2-link = Charles E. Leiserson | first2 = Charles E. | last2 = Leiserson | author3-link = Ronald L. Rivest | first3 = Ronald L. | last3 = Rivest | author4-link = Clifford Stein | first4 = Clifford | last4 = Stein | title = Introduction to Algorithms | edition = Second | publisher = [[MIT Press]] and [[McGraw–Hill]] | year = 2001 | isbn = 0-262-03293-7 | chapter = Section 24.3: Dijkstra's algorithm | pages = 595–601 | title-link = Introduction to Algorithms }}
-* {{cite journal | authorlink = Edsger W. Dijkstra | first1 = E. W. | last1 = Dijkstra | url= http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf | title = A note on two problems in connexion with graphs | journal = Numerische Mathematik | volume = 1 | year = 1959 | pages = 269–271 | ref = harv | doi = 10.1007/BF01386390}}
+* {{cite journal
-* {{cite book | author1-link = Thomas H. Cormen | first1 = Thomas H. | last1 = Cormen | author2-link = Charles E. Leiserson | first2 = Charles E. | last2 = Leiserson | author3-link = Ronald L. Rivest | first3 = Ronald L. | last3 = Rivest | author4-link = Clifford Stein | first4 = Clifford | last4 = Stein | title = [[Introduction to Algorithms]] | edition = Second | publisher = [[MIT Press]] and [[McGraw-Hill]] | year = 2001 | isbn = 0-262-03293-7 | chapter = Section 24.3: Dijkstra's algorithm | pages = 595–601}}
+ | last = Dial | first = Robert B.
-* {{cite journal|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=25th Annual Symposium on Foundations of Computer Science|year=1984|publisher=[[IEEE]]|pages=338-346|url=http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934|ref=harv|doi=10.1109/SFCS.1984.715934|access-date=2011-09-12|archive-date=2012-10-11|archive-url=https://web.archive.org/web/20121011090757/http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1984.715934|url-status=dead}}
+ | s2cid = 6754003
-* {{cite journal|first1=Michael Lawrence|last1=Fredman|authorlink1=Michael Fredman|first2=Robert E.|last2=Tarjan|authorlink2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the Association for Computing Machinery|volume=34|year=1987|pages=596-615|url=http://portal.acm.org/citation.cfm?id=28874|ref=harv|doi=10.1145/28869.28874|issue=3}}
+ | doi = 10.1145/363269.363610
-* {{cite journal | first1 = F. Benjamin | last1 = Zhan | first2 = Charles E. | last2 = Noon | month =February | year = 1998 | title = Shortest Path Algorithms: An Evaluation Using Real Road Networks | journal = [[Transportation Science]] | volume = 32 | issue = 1 | pages = 65–73 | doi = 10.1287/trsc.32.1.65}}
+ | url = https://dl.acm.org/doi/10.1145/363269.363610
-* {{cite book|first1=M.|last1=Leyzorek|first2=R. S.|last2=Gray|first3=A. A.|last3=Johnson|first4=W. C.|last4=Ladew|first5=S. R.|last5=Meaker, Jr.|first6=R. M.|last6=Petry|first7=R. N.|last7=Seitz|title=Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems|publisher=Case Institute of Technology|location=Cleveland, Ohio|year=1957|ref=harv}}
+ | url-access = subscription
+ | issue = 11
+ | journal = [[Communications of the ACM]]
+ | pages = 632–633
+ | title = Algorithm 360: Shortest-path forest with topological ordering [H]
+ | volume = 12
+ | year = 1969
+ }}
+* {{cite conference|first1=Michael Lawrence|last1=Fredman|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}}
+* {{cite journal|first1=Michael Lawrence|last1=Fredman|author-link1=Michael Fredman|first2=Robert E.|last2=Tarjan|s2cid=7904683|author-link2=Robert Tarjan|title=Fibonacci heaps and their uses in improved network optimization algorithms|journal=Journal of the Association for Computing Machinery|volume=34|year=1987|pages=596–615|doi=10.1145/28869.28874|issue=3}}
+* {{cite journal | first1 = F. Benjamin | last1 = Zhan | first2 = Charles E. | last2 = Noon | s2cid = 14986297 |date=February 1998 | title = Shortest Path Algorithms: An Evaluation Using Real Road Networks | journal = [[Transportation Science]] | volume = 32 | issue = 1 | pages = 65–73 | doi = 10.1287/trsc.32.1.65}}
+* {{cite book|first1=M.|last1=Leyzorek|first2=R. S.|last2=Gray|first3=A. A.|last3=Johnson|first4=W. C.|last4=Ladew|first5=S. R.|last5=Meaker, Jr.|first6=R. M.|last6=Petry|first7=R. N.|last7=Seitz|title=Investigation of Model Techniques – First Annual Report – 6 June 1956 – 1 July 1957 – A Study of Model Techniques for Communication Systems|publisher=Case Institute of Technology|location=Cleveland, Ohio|year=1957}}
+* {{cite journal|first1=D.E.|last1=Knuth|title=A Generalization of Dijkstra's Algorithm|journal=[[Information Processing Letters]]|volume=6|number=1|pages=1–5|year=1977|author-link1=Donald Knuth|doi=10.1016/0020-0190(77)90002-3}}
+* {{cite journal|first1=Ravindra K.|last1=Ahuja|first2=Kurt|last2=Mehlhorn|first3=James B.|last3=Orlin|first4=Robert E.|last4=Tarjan|s2cid=5499589|title=Faster Algorithms for the Shortest Path Problem|journal=Journal of the ACM|volume=37|number=2|pages=213–223| date=April 1990 |doi=10.1145/77600.77615|url=https://dspace.mit.edu/bitstream/1721.1/47994/1/fasteralgorithms00sloa.pdf|hdl=1721.1/47994|hdl-access=free}}
+* {{cite journal|first1=Rajeev|last1=Raman|s2cid=18031586|title=Recent results on the single-source shortest paths problem|journal=SIGACT News|volume=28|issue=2|pages=81–87|year=1997|doi=10.1145/261342.261352}}
+* {{cite journal|first1=Mikkel|last1=Thorup|s2cid=5221089|title=On RAM priority Queues|journal=SIAM Journal on Computing|volume=30|issue=1|pages=86–109|year=2000|doi=10.1137/S0097539795288246}}
+* {{cite journal|first1=Mikkel|last1=Thorup|s2cid=207654795|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|year=1999|doi=10.1145/316542.316548|url=http://www.diku.dk/~mthorup/PAPERS/sssp.ps.gz}}
 == แหล่งข้อมูลอื่น ==