อัลกอริทึม Shortest Path ในเครือข่ายคอมพิวเตอร์

ในเครือข่ายคอมพิวเตอร์ อัลกอริทึม shortest path มีเป้าหมายเพื่อหาเส้นทางที่เหมาะสมที่สุดระหว่างโหนดเครือข่าย เพื่อให้ routing cost ต่ำสุด พวกเขาเป็น direct applications ของ shortest path algorithms ที่เสนอใน graph theory

คำอธิบาย

พิจารณาว่าเครือข่ายประกอบด้วย N vertices (โหนดหรืออุปกรณ์เครือข่าย) ที่เชื่อมต่อโดย M edges (สายส่ง) แต่ละ edge มีน้ำหนัก แทนระยะทางทางกายภาพหรือ transmission delay ของสายส่ง เป้าหมายของ shortest path algorithms คือหาเส้นทางระหว่างคู่ vertices ใดๆ ตาม edges จนผลรวมน้ำหนักของ edges ต่ำสุด หาก edges มีน้ำหนักเท่ากัน shortest path algorithm จะหาเส้นทางที่มีจำนวน hops น้อยที่สุด

Common Shortest Path Algorithms (อัลกอริทึม shortest path ทั่วไป)

อัลกอริทึม shortest path ทั่วไปมีดังนี้ −

• Bellman Ford's Algorithm

• Dijkstra's Algorithm

• Floyd Warshall's Algorithm

ส่วนต่อไปอธิบายแต่ละอัลกอริทึม

Bellman Ford Algorithm

Input − กราฟแทนเครือข่าย; และ source node, s

Output − Shortest path จาก s ไปยังโหนดอื่นทั้งหมด

• Initialize distances จาก s ไปยังทุกโหนดเป็น infinite (∞); ระยะทางไปตัวเองเป็น 0; อาร์เรย์ dist[] ขนาด |V| (จำนวนโหนด) ทุกค่าเป็น ∞ ยกเว้น dist[s]

• คำนวณ shortest distances แบบ iterative ทำซ้ำ |V|- 1 ครั้ง สำหรับแต่ละโหนดยกเว้น s −

  • ทำซ้ำสำหรับแต่ละ edge ที่เชื่อม vertices u และ v −

    • หาก dist[v] > (dist[u] + weight of edge u-v) แล้ว

      • อัปเดต dist[v] = dist[u] + weight of edge u-v

• อาร์เรย์ dist[] มี shortest path จาก s ไปยังทุกโหนดอื่น

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 ไปยังทุกโหนดอื่น

Floyd Warshall Algorithm

Input − Cost adjacency matrix adj[][] แทนเส้นทางระหว่างโหนดในเครือข่าย

Output − Shortest path cost matrix cost[][] แสดง shortest paths ในแง่ของ cost ระหว่างแต่ละคู่โหนดในกราฟ

• เติม cost[][] ดังนี้:

  • หาก adj[][] ว่าง แล้ว cost[][] = ∞

  • มิฉะนั้น cost[][] = adj[][]

• N = |V| โดย V แทนเซตของโหนดในเครือข่าย

• ทำซ้ำสำหรับ k = 1 to N −

  • ทำซ้ำสำหรับ i = 1 to N −

    • ทำซ้ำสำหรับ j = 1 to N −

      • หาก cost[i][k] + cost[k][j] < cost[i][j] แล้ว

        • อัปเดต cost[i][j] := cost[i][k] + cost[k][j]

• Matrix cost[][] มี shortest cost จากแต่ละโหนด i ไปยังทุกโหนด j