ขั้นตอนวิธี dextra และการใช้งาน
ในวิชาคณิตศาสตร์และวิทยาศาสตร์คอมพิวเตอร์มีทิศทางที่เรียกว่าทฤษฎีกราฟ ภายในกรอบงานมีการกำหนดและแก้ไขปัญหาต่างๆเช่นหาเส้นทางที่สั้นที่สุดระหว่างจุดยอด หนึ่งในวิธีที่พบมากที่สุดในการแก้ปัญหานี้ในหมู่นักคณิตศาสตร์ได้เป็นขั้นตอน Dijkstra แล้ว
เป็นที่เชื่อกันว่าความคิดของกราฟถูกนำมาใช้การใช้ในศตวรรษที่สิบแปดโดย Leonard Euler ผู้ที่เปล่งออกมาเป็นผู้กำหนดและแก้ปัญหาหนึ่งในปัญหาคลาสสิกของทฤษฎีนี้ - เกี่ยวกับสะพานเจ็ดแห่งของ Koenigsberg เพื่อที่จะอธิบายถึงวัตถุประสงค์ของทฤษฎีนี้ส่วนใหญ่มักใช้ความคล้ายคลึงกันเช่นการเคลื่อนไหวระหว่างเมืองต่างๆ จากนั้นกราฟบนเครื่องบินจะแสดงแผนผังทั้งหมดของเส้นทางซึ่งจุดจะเป็นจุดเฉพาะ (เช่นเมือง) และขอบ - เส้นทางจากจุดสูงสุดไปอีก (คล้ายคลึงกับถนนระหว่างเมือง) อัลกอริทึมของ Dijkstra นอกเหนือจากวิธีการอื่น ๆ สามารถให้คำตอบสำหรับคำถามนี้ได้
หนึ่งในปัญหามาตรฐานของทฤษฎีกราฟคือหนึ่งที่มีความจำเป็นในการกำหนดเส้นทางที่คุ้มค่าระหว่างสองจุด สามารถลดลงบนเครื่องบินเพื่อแก้ปัญหาของกราฟซึ่งจุดยอด - เมืองจะเชื่อมต่อกันด้วยขอบซึ่งเป็นตัวแทนของถนนที่เป็นไปได้ และแต่ละถนนมีความยาวของตัวเองดังนั้นการเดินทางผ่านจะต้องใช้จ่ายเงินจำนวนหนึ่ง ผลรวมนี้เทียบเท่ากับน้ำหนักของขอบบนกราฟ จากนั้นปัญหาในทางปฏิบัติสามารถกำหนดได้ดังต่อไปนี้: วิธีปูทางจากเมืองหนึ่งไปยังอีกเมืองหนึ่งเพื่อใช้จ่ายเงินน้อยที่สุด
วิธีการที่จะแก้ปัญหา
เพื่อแก้ปัญหานี้บ้างอัลกอริทึมที่เป็นที่รู้จักอย่างแพร่หลายในโลกวิทยาศาสตร์ ตัวอย่างเช่นขั้นตอนวิธี Floyd - Warshell, Ford - Bellman อัลกอริธึม Dijkstra ยังเป็นวิธีที่คลาสสิกในการหาโซลูชัน นอกจากนี้ยังสามารถใช้สำหรับกราฟที่มีน้ำหนัก (น้ำหนักของแต่ละขอบ) และสำหรับเบาบาง ในการหาเส้นทางสุดท้ายคุณต้องทำตามขั้นตอน
อัลกอริทึม Dijkstra
ความหมายของวิธีนี้ก็คือจุดยอดทั้งหมดจะถูกข้ามโดยเริ่มต้นจากจุดที่กำหนดแต่ละอันจะได้รับป้ายกำกับที่มีค่าบางอย่าง จากนั้นผลลัพธ์จะมีจุดยอดที่มีป้ายกำกับน้อยที่สุด ในขั้นตอนแรกจุดยอดต้นจะได้รับการกำหนดป้ายชื่อที่มีค่าเป็น 0 จากนั้นจุดยอดทั้งหมดต่อไปนี้จะถือว่าเป็นจุดที่สามารถเข้าถึงได้จากจุดสุดยอดดั้งเดิม พวกเขาได้รับการกำหนดป้ายชื่อที่มีค่าถูกกำหนดเป็นผลรวมของแหล่งที่มาและน้ำหนักของเส้นทาง จากจุดยอดของขั้นตอนถัดไปจะได้รับการเลือกหนึ่งที่มีค่าน้อยที่สุดของป้ายกำกับและจุดยอดทั้งหมดที่สามารถข้ามผ่านได้โดยไม่ต้องใช้จุดศูนย์กลางระดับกลาง มีการกำหนดค่าใหม่ของป้ายกำกับเท่ากับป้ายกำกับของจุดยอดต้นทางบวกน้ำหนักของเส้นทาง หากค่าที่ได้คือน้อยกว่าป้ายจุดสุดยอดป้ายกำกับจะเปลี่ยนไป มิฉะนั้นค่าเดิมจะยังคงอยู่ ในกรณีนี้ในอาร์เรย์ที่แยกต่างหากซึ่งมีมิติเท่ากับจำนวนจุดยอดของกราฟผลลัพธ์ของการเพิ่มประสิทธิภาพจะถูกเก็บรักษาไว้ตามเส้นทางที่กำหนดไว้ เพื่อใช้วิธีการดังกล่าวเป็นอัลกอริธึม Dijkstra Pascal มีเครื่องมือที่สะดวกมาก อัลกอริทึมมีข้อดีที่สามารถใช้เป็นพื้นฐานของโปรแกรมที่มีขนาดเล็กได้ ตัวอย่างผลิตภัณฑ์ซอฟต์แวร์ดังกล่าวสามารถหาได้ง่ายบนอินเทอร์เน็ต
