Definition (นิยาม)
Dijkstra's algorithm หา shortest path จากโหนดเฉพาะที่เรียกว่า source node ไปยังทุกโหนดใน connected graph สร้าง shortest path tree ที่มี source node เป็น root ใช้กันอย่างแพร่หลายในเครือข่ายคอมพิวเตอร์เพื่อสร้างเส้นทางที่เหมาะสมที่สุดเพื่อลด routing costs
Dijkstra's Algorithm
Input − กราฟแทนเครือข่าย; และ source node, s
Output − Shortest path tree, spt[], ที่มี s เป็น root node
Initializations −
อาร์เรย์ระยะทาง dist[] ขนาด |V| โดย dist[s] = 0 และ dist[u] = ∞ โดย u คือโหนดในกราฟยกเว้น s
อาร์เรย์ Q มีทุกโหนดในกราฟ เมื่ออัลกอริทึมเสร็จ Q จะว่าง
เซตว่าง S ที่จะเพิ่มโหนดที่เยี่ยมชมแล้ว เมื่ออัลกอริทึมเสร็จ S จะมีทุกโหนดในกราฟ
ทำซ้ำขณะ Q ไม่ว่าง −
นำออกจาก Q โหนด u ที่มี dist[u] น้อยที่สุดและไม่อยู่ใน S ในรอบแรก dist[s] ถูกนำออก
เพิ่ม u เข้า S ทำเครื่องหมาย u ว่าเยี่ยมชมแล้ว
สำหรับโหนด v ที่ติดจำนวนกับ u อัปเดต dist[v] ดังนี้ −
หาก (dist[u] + weight of edge u-v) < dist[v], แล้ว
อัปเดต dist[v] = dist[u] + weight of edge u-v
อาร์เรย์ dist[] มี shortest path จาก s ไปยังทุกโหนดอื่น
Example (ตัวอย่าง)
การทำงานของอัลกอริทึมเข้าใจได้ดีที่สุดจากตัวอย่าง พิจารณากราฟต่อไปนี้ที่มีโหนด A ถึง G เชื่อมต่อด้วย weighted edges ดังนี้ −
Initializations จะเป็นดังนี้ −
dist[7]={0,∞,∞,∞,∞,∞,∞}
Q={A,B,C,D,E,F,G}
S= ∅
Pass 1 − เราเลือกโหนด A จาก Q เนื่องจากมี dist[] ต่ำสุดคือ 0 ใส่ใน S โหนดติดจำนวนของ A คือ B และ C อัปเดต dist[] สำหรับ B และ C ตามอัลกอริทึม ค่าของ data structures กลายเป็น −
dist[7]={0,5,6,∞,∞,∞,∞}
Q={B,C,D,E,F,G}
S={A}
ระยะทางและ shortest paths หลัง pass นี้แสดงในกราฟ โหนดสีเขียวแทนโหนดที่เพิ่มใน S แล้ว −
Pass 2 − เราเลือกโหนด B จาก Q เนื่องจากมี dist[] ต่ำสุดคือ 5 ใส่ใน S. โหนดติดจำนวนของ B คือ C, D และ E อัปเดต dist[] สำหรับ C, D และ E ตามอัลกอริทึม ค่า data structures กลายเป็น −
dist[7]={0,5,6,12,13,∞,∞}
Q={C,D,E,F,G}
S={A,B}
ระยะทางและ shortest paths หลัง pass นี้ −
Pass 3 − เราเลือกโหนด C จาก Q เนื่องจากมี dist[] ต่ำสุดคือ 6 ใส่ใน S โหนดติดจำนวนของ C คือ D และ F อัปเดต dist[] สำหรับ D และ F ค่า data structures กลายเป็น −
dist[7]={0,5,6,8,13,10,∞}
Q={D,E,F,G}
S={A,B,C}
ระยะทางและ shortest paths หลัง pass นี้ −
Pass 4 − เราเลือกโหนด D จาก Q เนื่องจากมี dist[] ต่ำสุดคือ 8 ใส่ใน S โหนดติดจำนวนของ D คือ E, F และ G อัปเดต dist[] สำหรับ E, F และ G ค่า data structures กลายเป็น −
dist[7]={0,5,6,8,10,10,18}
Q={E,F,G}
S={A,B,C,D}
ระยะทางและ shortest paths หลัง pass นี้ −
Pass 5 − เราสามารถเลือกโหนด E หรือ F จาก Q ได้ เนื่องจากทั้งคู่มี dist[] ต่ำสุดคือ 10 เราเลือกหนึ่งในนั้น สมมติ E ใส่ใน S โหนดติดจำนวนของ D คือ G อัปเดต dist[] สำหรับ G ค่า data structures กลายเป็น −
dist[7]={0,5,6,8,10,10,13}
Q={F,G}
S={A,B,C,D,E}
ระยะทางและ shortest paths หลัง pass นี้ −
Pass 6 − เราเลือกโหนด F จาก Q เนื่องจากมี dist[] ต่ำสุดคือ 10 ใส่ใน S โหนดติดจำนวนของ F คือ G ค่า dist[] ของ G น้อยกว่าที่จะผ่าน F จึงคงเดิม ค่า data structures กลายเป็น −
dist[7]={0,5,6,8,10,10,13}
Q={G}
S={A,B,C,D,E,F}
ระยะทางและ shortest paths หลัง pass นี้ −
Pass 7 − มีโหนดเดียวใน Q นำออกจาก Q ใส่ใน S อาร์เรย์ dist[] ไม่ต้องเปลี่ยน ตอนนี้ Q ว่าง S มีทุกโหนด จึงสิ้นสุดอัลกอริทึม เราตัด edges/เส้นทางที่ไม่อยู่ใน path ใดๆ shortest path tree จาก source node A ไปทุกโหนดอื่นเป็นดังนี้ −
