Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
บทความนี้ไม่มีจาก |
ขั้นตอนวิธีของไดก์สตรา (อังกฤษ: 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
การประยุกต์ใช้งาน
เราสามารถย่อส่วนปัญหาในชีวิตจริงให้เป็นปัญหาทางคณิตศาสตร์ได้ เช่น การให้จุดยอดเป็นเมืองและเส้นเชื่อมเป็นถนน
ดูเพิ่ม
- ขั้นตอนวิธีของเบลแมน-ฟอร์ด สำหรับปัญหาวิถีสั้นสุดที่น้ำหนักของเส้นเชื่อมติดลบได้
อ้างอิง
- ; ; ; (2001). "Section 24.3: Dijkstra's algorithm". (Second ed.). and . pp. 595–601. ISBN .
- Dial, Robert B. (1969). "Algorithm 360: Shortest-path forest with topological ordering [H]". . 12 (11): 632–633. doi:10.1145/363269.363610. S2CID 6754003.
- ; (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.
- ; (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". . 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". . 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. :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.
แหล่งข้อมูลอื่น
- ขั้นตอนวิธีของไดก์สตราในยูทูบ
 | บทความนี้ยังเป็น คุณสามารถช่วยวิกิพีเดียได้โดยการเพิ่มเติมข้อมูล หมายเหตุ: ขอแนะนำให้จัด (ดูเพิ่มที่ ) |
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 khntxnwithikhxngidkstra xngkvs Dijkstra s algorithm thukkhidkhnkhunodynkwithyakarkhxmphiwetxrchawdtchnamwa Edsger Dijkstra inpi 1959 ephuxaekikhpyhawithisnsudcakcudhnungid sahrbkrafthimikhwamyawkhxngesnechuxmimepnlb sahrbkhntxnwithinicaharayathangsnthisudcakcudhnungipyngcudid inkrafodycahaesnthangthisnthisudipthilacudyxderuxy cnkhrbtamthitxngkarkhntxnwithikhxngidkstrarupphaphaesdngkhntxnwithikhxngidkstrapraephthkhntxnwithikarkhnhaokhrngsrangkhxmulkrafprasiththiphaphemuxekidkrniaeythisudO E VlogV displaystyle O E VlogV kkhntxnwithikahndihpmhnungepnpmerimtn initial node aelakahndih rayathangkhxngpm Y distance of node Y hmaythungrayathangcakpmerimtnipyngpm Y khntxnwithikhxngidkstracakahndkharayathangerimtniwbangpmaelacaephimkhaipthilakhntxn kahndihthukpmmikharayathangtamesnechuxm odyihpmerimtnmikhaepnsuny aelapmxunmikhaepnxnnt thaekhruxnghmaythukpmykewnpmerimtnwayngimipeyuxn unvisited tngihpmerimtnepnpmpccubn srangestkhxngpmthiyngimipeyuxnkhunmaesthnungsungprakxbdwythukpmykewnpmerimtn cakpmpccubn phicarnapmkhangekhiyngtamesnechuxmthukpmthiyngimipeyuxn aelakhanwnrayathangtxenuxngkhxngesnechuxm twxyangechn thapmpccubnkhux A mirayathangkhxngpmepn 6 aelaesnechuxmthitxcak A ipyngpmkhangekhiyng B mirayathangepn 2 dngnnrayathangkhxngpm B odyphan A cungethakb 6 2 8 epntn tharayathangthikhanwnidmikhanxykwakharayathangthibnthukxyukhxngpmnn ihekhiynthbkharayathangkhxngpmdngklaw aemwapmkhangekhiyngidthukphicarnaaelw aetkyngimthaekhruxnghmaywaipeyuxnaelw visited inkhntxnni pmkhangekhiyngcayngkhngxyuinestkhxngpmthiyngimipeyuxnechnedim emuxphicarnapmkhangekhiyngcakpmpccubnkhrbthukpmaelw thaekhruxnghmaypmpccubnwaipeyuxnaelw aelanaxxkcakestkhxngpmthiyngimipeyuxn pmthiipeyuxnaelwnicaimthuknamatrwcsxbxik kharayathangthibnthukxyucasinsudaelamikhanxysud pmpccubntwthdipthithukeluxkcaepnpmthimikharayathangnxysudinestkhxngpmthiyngimipeyuxn thaestkhxngpmthiyngimipeyuxnfwangaelwihhyudkarthangan khntxnwithiesrcsin hakimichiheluxkpmyngimipeyuxnthimikharayathangnxysudepnpmpccubn aelwwnklbipthakhntxnthi 3karprayuktichnganerasamarthyxswnpyhainchiwitcringihepnpyhathangkhnitsastrid echn karihcudyxdepnemuxngaelaesnechuxmepnthnnduephimkhntxnwithikhxngeblaemn fxrd sahrbpyhawithisnsudthinahnkkhxngesnechuxmtidlbidxangxing 2001 Section 24 3 Dijkstra s algorithm Second ed and pp 595 601 ISBN 0 262 03293 7 Dial Robert B 1969 Algorithm 360 Shortest path forest with topological ordering H 12 11 632 633 doi 10 1145 363269 363610 S2CID 6754003 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 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 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 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 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 aehlngkhxmulxunkhntxnwithikhxngidkstrainyuthubbthkhwamniyngepnokhrng khunsamarthchwywikiphiediyidodykarephimetimkhxmul hmayehtu khxaenanaihcdhmwdhmuokhrngihekhakbenuxhakhxngbthkhwam duephimthi wikiphiediy okhrngkarcdhmwdhmuokhrngthiyngimsmburn dkhk