คำจำกัดความ
อัลกอริทึมของ Dijkstra ค้นหาเส้นทางที่สั้นที่สุดจากโหนดใดโหนดหนึ่ง ซึ่งเรียกว่าโหนดต้นทางไปยังโหนดอื่นๆ ในกราฟที่เชื่อมต่อ มันสร้างแผนผังเส้นทางที่สั้นที่สุดโดยมีโหนดต้นทางเป็นรูท มีการใช้อย่างลึกซึ้งในเครือข่ายคอมพิวเตอร์เพื่อสร้างเส้นทางที่เหมาะสมที่สุดโดยมีเป้าหมายเพื่อลดต้นทุนการกำหนดเส้นทาง
อัลกอริทึมของ Dijkstra
อินพุต - กราฟแสดงเครือข่าย และโหนดต้นทาง s
เอาต์พุต - ต้นไม้พาธที่สั้นที่สุด spt[] โดยมี s เป็นโหนดรูท
การเริ่มต้น -
-
อาร์เรย์ของระยะทาง dist[] ขนาด |V| (จำนวนโหนด) โดยที่ dist[s] =0 และ dist[u] =∞ (อนันต์) โดยที่ u แทนโหนดในกราฟ ยกเว้น s.
-
อาร์เรย์ Q ซึ่งประกอบด้วยโหนดทั้งหมดในกราฟ เมื่ออัลกอริทึมทำงานเสร็จสิ้น Q จะว่างเปล่า
-
ชุดว่าง S ซึ่งโหนดที่เข้าชมจะถูกเพิ่มเข้าไป เมื่ออัลกอริทึมทำงานเสร็จสิ้น S จะมีโหนดทั้งหมดในกราฟ
-
ทำซ้ำในขณะที่ Q ไม่ว่าง -
-
ลบออกจาก Q , โหนด, คุณมี dist[u] ที่เล็กที่สุด และที่ไม่อยู่ใน S ในการรันครั้งแรก dist[s] ถูกลบออก
-
เพิ่มคุณใน S ทำเครื่องหมายว่าเยี่ยมชมแล้ว
-
สำหรับแต่ละโหนด v ซึ่งอยู่ติดกับ u ให้อัพเดต dist[v] เป็น −
-
ถ้า (dist[u] + น้ำหนักของขอบ u-v )
-
อัปเดต dist[v] =dist[u] + น้ำหนักของ edge u-v
-
-
-
-
อาร์เรย์ dist[] มีเส้นทางที่สั้นที่สุดจาก s ไปยังโหนดอื่น ๆ ทุกโหนด
ตัวอย่าง
การทำงานของอัลกอริทึมสามารถเข้าใจได้ดีที่สุดโดยใช้ตัวอย่าง พิจารณากราฟต่อไปนี้ที่มีโหนดที่ทำเครื่องหมายจาก A ถึง G ซึ่งเชื่อมต่อกันด้วยขอบถ่วงน้ำหนักดังนี้ −
การเริ่มต้นจะเป็นดังนี้ -
-
dist[7]={0,∞,∞,∞,∞,∞,∞}
-
Q={A,B,C,D,E,F,G}
-
ส𝑆=∅
ผ่าน 1 − เราเลือกโหนด A จาก Q เนื่องจากมีค่าต่ำสุด dist[] ค่าของ 0 และใส่ไว้ใน S โหนดข้างเคียงของ A คือ B และ C เราอัปเดตค่า dist[] ที่สอดคล้องกับ B และ C ตามอัลกอริทึม ดังนั้นค่าของโครงสร้างข้อมูลจึงกลายเป็น −
-
dist[7]={0,5,6,∞,∞,∞,∞}
-
Q={B,C,D,E,F,G}
-
S={A}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้ แสดงในกราฟต่อไปนี้ โหนดสีเขียวหมายถึงโหนดที่เพิ่มไปยัง S แล้ว -
ผ่าน 2 − เราเลือกโหนด B จาก Q เนื่องจากมีค่าต่ำสุด dist[] ค่า 5 แล้วใส่ S. โหนดข้างเคียงของ B คือ C, D และ อี . เราอัปเดตค่า dist[] ที่สอดคล้องกับ C, D และ E ตามอัลกอริทึม ดังนั้นค่าของโครงสร้างข้อมูลจึงกลายเป็น −
-
dist[7]={0,5,6,12,13,∞,∞}
-
Q={C,D,E,F,G}
-
S={A,B}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้คือ −
ผ่าน 3 − เราเลือกโหนด C จาก Q เนื่องจากมีค่า dist[] ต่ำสุดที่ 6 และใส่ไว้ใน S โหนดข้างเคียงของ C คือ D และ F เราอัปเดตค่า dist[] ที่สอดคล้องกับ D และ F ดังนั้นค่าของโครงสร้างข้อมูลจึงกลายเป็น -
-
dist[7]={0,5,6,8,13,10,∞}
-
Q={D,E,F,G}
-
S={A,B,C}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้คือ −
ผ่าน 4 − เราเลือกโหนด D จาก Q เนื่องจากมี dist[ . ต่ำสุด[ ] ค่า 8 และใส่ไว้ใน S โหนดข้างเคียงของ D คือ E, F และ G เราอัปเดต dist[] ค่าที่สอดคล้องกับ E, F และ G . ดังนั้นค่าของโครงสร้างข้อมูลจึงกลายเป็น −
-
dist[7]={0,5,6,8,10,10,10,18}
-
Q={E,F,G}
-
S={A,B,C,D}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้คือ −
ผ่าน 5 − เราสามารถเลือกโหนด E หรือโหนด F จาก Q เนื่องจากทั้งคู่มี dist[] . ต่ำที่สุด มูลค่า 10 . เราเลือกอันใดอันหนึ่งพูดว่า E และใส่ใน S . โหนดข้างเคียงของ D คือ G . เราอัปเดต dist[] ค่าที่สอดคล้องกับ G ดังนั้นค่าของโครงสร้างข้อมูลจึงกลายเป็น -
-
dist[7]={0,5,6,8,10,10,13}
-
Q={F,G}
-
S={A,B,C,D,E}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้คือ −
ผ่าน 6 − เราเลือกโหนด F จาก Q เนื่องจากมี dist[] . ต่ำสุด ค่า 10 แล้วใส่ S . โหนดข้างเคียงของ F คือ G . dist[] ค่าที่สอดคล้องกับ G น้อยกว่าค่าผ่าน F . ดังนั้นมันจึงยังคงเหมือนเดิม ค่าของโครงสร้างข้อมูลจะกลายเป็น −
-
dist[7]={0,5,6,8,10,10,13}
-
Q={G}
-
S={A,B,C,D,E,F}
ระยะทางและเส้นทางที่สั้นที่สุดหลังจากผ่านนี้คือ −
ผ่าน 7 − มีเพียงโหนดเดียวใน Q . เราลบออกจาก Q ใส่ไว้ใน S. อาร์เรย์ dist[] ไม่จำเป็นต้องเปลี่ยนแปลง ตอนนี้ Q ว่างเปล่า S มีโหนดทั้งหมดและเรามาถึงจุดสิ้นสุดของอัลกอริทึม เราขจัดขอบหรือเส้นทางทั้งหมดที่ไม่ได้อยู่ในเส้นทางของเส้นทางใด ๆ ดังนั้นแผนผังเส้นทางที่สั้นที่สุดจากโหนดต้นทาง A ไปยังโหนดอื่นทั้งหมดมีดังนี้ -
