อัลกอริทึมเส้นทางที่สั้นที่สุดในเครือข่ายคอมพิวเตอร์

ในเครือข่ายคอมพิวเตอร์ อัลกอริธึมพาธที่สั้นที่สุดมีเป้าหมายเพื่อค้นหาเส้นทางที่เหมาะสมที่สุดระหว่างโหนดเครือข่าย เพื่อลดต้นทุนการเราต์ เป็นการใช้งานโดยตรงของอัลกอริธึมพาธที่สั้นที่สุดที่เสนอในทฤษฎีกราฟ

คำอธิบาย

พิจารณาว่าเครือข่ายประกอบด้วยจุดยอด N (โหนดหรืออุปกรณ์เครือข่าย) ที่เชื่อมต่อด้วยขอบ M (สายส่งสัญญาณ) ขอบแต่ละด้านสัมพันธ์กับน้ำหนัก ซึ่งแสดงถึงระยะห่างทางกายภาพหรือความล่าช้าในการส่งของสายส่ง เป้าหมายของอัลกอริธึมพาธที่สั้นที่สุดคือการหาเส้นทางระหว่างจุดยอดคู่ใดๆ ตามขอบ ดังนั้นผลรวมของน้ำหนักของขอบจะน้อยที่สุด หากขอบมีน้ำหนักเท่ากัน อัลกอริธึมเส้นทางที่สั้นที่สุดจะมุ่งหมายเพื่อค้นหาเส้นทางที่มีจำนวนการกระโดดขั้นต่ำ

อัลกอริธึมพาธทั่วไปที่สั้นที่สุด

อัลกอริธึมพาธที่สั้นที่สุดทั่วไปคือ -

• อัลกอริธึมของ Bellman Ford

• อัลกอริทึมของ Dijkstra

• อัลกอริธึมของ Floyd Warshall

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

เบลล์แมนฟอร์ดอัลกอริทึม

อินพุต - กราฟแสดงเครือข่าย และโหนดต้นทาง s

เอาต์พุต - เส้นทางที่สั้นที่สุดจาก s ไปยังโหนดอื่นทั้งหมด

• เริ่มต้นระยะทางจาก s ถึงโหนดทั้งหมดเป็นอนันต์ (∞); ระยะห่างกับตัวเองเป็น 0; อาร์เรย์ dist[] ขนาด |V| (จำนวนโหนด) โดยมีค่าทั้งหมดเป็น ∞ ยกเว้น dist[s] .

• คำนวณระยะทางที่สั้นที่สุดซ้ำๆ ทำซ้ำ |V|- 1 ครั้งสำหรับแต่ละโหนดยกเว้น s -

  • ทำซ้ำสำหรับแต่ละขอบที่เชื่อมต่อจุดยอด u และ v -

    • ถ้า dist[v]> (dist[u] + น้ำหนักของขอบ u-v) แล้ว

      • อัปเดต dist[v] =dist[u] + น้ำหนักของ edge u-v

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

อัลกอริทึมของ 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[v] =dist[u] + น้ำหนักของ edge u-v

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

อัลกอริทึมของ Floyd Warshall

อินพุต - เมทริกซ์ที่อยู่ติดกันต้นทุน adj[][] แสดงถึงเส้นทางระหว่างโหนดในเครือข่าย

ผลลัพธ์ - เมทริกซ์ต้นทุนเส้นทางที่สั้นที่สุด ต้นทุน[][] แสดงเส้นทางที่สั้นที่สุดในแง่ของต้นทุนระหว่างโหนดแต่ละคู่ในกราฟ

• เติม ค่าใช้จ่าย[][] ดังนี้

  • ถ้า adj[][] ว่างเปล่า จากนั้น ค่าใช้จ่าย[][] =∞ (อนันต์)

  • ค่าใช้จ่าย[][] =adj[][]

• ไม่มี =|V| โดยที่ วี แสดงถึงชุดของโหนดในเครือข่าย

• ทำซ้ำสำหรับ k =1 ถึง N −

  • ทำซ้ำสำหรับ i =1 ถึง N −

    • ทำซ้ำสำหรับ j =1 ถึง N −

      • ถ้า ค่าใช้จ่าย[i][k] + ราคา[k][j] <ค่าใช้จ่าย[i][j] แล้ว

        • อัปเดต ค่าใช้จ่าย[i][j] :=ค่าใช้จ่าย[i][k] + ราคา[k][j]

• เมทริกซ์ ค่าใช้จ่าย[][] มีต้นทุนที่สั้นที่สุดจากแต่ละโหนด i ไปยังโหนดอื่นทุกโหนด j .