fbpx
วิกิพีเดีย

ขั้นตอนวิธีของไดก์สตรา

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

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

ขั้นตอนวิธี

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

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

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

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

ดูเพิ่ม

อ้างอิง

  • Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390.CS1 maint: ref=harv (link)
  • 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.
  • Fredman, Michael Lawrence; Tarjan, Robert E. (1984). . 25th Annual Symposium on Foundations of Computer Science. IEEE: 338–346. doi:10.1109/SFCS.1984.715934. คลังข้อมูลเก่า เก็บจาก แหล่งเดิม เมื่อ 2012-10-11. สืบค้นเมื่อ 2011-09-12.CS1 maint: ref=harv (link)
  • 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.CS1 maint: ref=harv (link)
  • Zhan, F. Benjamin; Noon, Charles E. (1998). "Shortest Path Algorithms: An Evaluation Using Real Road Networks". Transportation Science. 32 (1): 65–73. doi:10.1287/trsc.32.1.65. Unknown parameter |month= ignored (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.CS1 maint: ref=harv (link)

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

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

นตอนว, ของไดก, สตรา, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, งกฤษ, dijkstra, . bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir khntxnwithikhxngidkstra xngkvs Dijkstra s algorithm thukkhidkhnkhunodynkwithyakarkhxmphiwetxrchawdtchnamwa aexdsekhxr idkstra Edsger Dijkstra inpi 1959 ephuxaekikhpyhawithisnsudcakcudhnungid sahrbkrafthimikhwamyawkhxngesnechuxmimepnlb sahrbkhntxnwithinicaharayathangsnthisudcakcudhnungipyngcudid inkrafodycahaesnthangthisnthisudipthilacudyxderuxy cnkhrbtamthitxngkarkhntxnwithikhxngidkstrarupphaphaesdngkhntxnwithikhxngidkstrapraephthkhntxnwithikarkhnhaokhrngsrangkhxmulkrafprasiththiphaphemuxekidkrniaeythisudO E V l o g V displaystyle O E VlogV dkhk enuxha 1 khntxnwithi 2 karprayuktichngan 3 duephim 4 xangxing 5 aehlngkhxmulxunkhntxnwithi aekikhkahndihpmhnungepnpmerimtn 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 3karprayuktichngan aekikherasamarthyxswnpyhainchiwitcringihepnpyhathangkhnitsastrid echn karihcudyxdepnemuxngaelaesnechuxmepnthnnduephim aekikhkhntxnwithikhxngeblaemn fxrd sahrbpyhawithisnsudthinahnkkhxngesnechuxmtidlbid pyhakaredinthangkhxngphnkngankhayxangxing aekikhDijkstra E W 1959 A note on two problems in connexion with graphs PDF Numerische Mathematik 1 269 271 doi 10 1007 BF01386390 CS1 maint ref harv link 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 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 khlngkhxmuleka ekbcak aehlngedim emux 2012 10 11 subkhnemux 2011 09 12 CS1 maint ref harv link 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 CS1 maint ref harv link Zhan F Benjamin Noon Charles E 1998 Shortest Path Algorithms An Evaluation Using Real Road Networks Transportation Science 32 1 65 73 doi 10 1287 trsc 32 1 65 Unknown parameter month ignored 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 CS1 maint ref harv link aehlngkhxmulxun aekikhkhntxnwithikhxngidkstrainyuthub bthkhwamniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmulekhathungcak https th wikipedia org w index php title khntxnwithikhxngidkstra amp oldid 9561035, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม