กราฟถ่วงน้ำหนัก

      ตัวอย่าง กราฟต่อไปนี้เป็นถ่วงน้ำหนัก

       ตัวอย่าง 

    กราฟต่อไปนี้เป็นกราฟถ่วงน้ำหนัก ซึ่งจำลองจากแผนที่เมืองในประเทศไทย

โดยให้จุดยอดแทนเมือง เส้นเชื่อมแทนถนน และค่าน้ำหนักเส้นเชื่อมแทนระยะทางระหว่าง

เมืองสองเมือง

            จะหาเส้นทางจากเมือง  A ไปยังเมือง E ทั้งหมดที่ไม่ผ่านเมืองซ้ำกัน

              เส้นทางที่   1 A, B, D, E ระยะทางยาว 2 + 1 + 3 = 4 กิโลเมตร

            เส้นทางที่   2 A, B, D, F, E ระยะทางยาว 2 + 1 + 2 + 2 = 7 กิโลเมตร

            เส้นทางที่   3 A, B, D, C, F, E ระยะทางยาว 2 + 1 + 3 + 6 + 2 = 14 กิโลเมตร

            เส้นทางที่   4 A, C, F, E ระยะทางยาว 5 + 6 + 2 = 13 กิโลเมตร

            เส้นทางที่   5 A, C, F, D, E ระยะทางยาว 5 + 6 + 2 + 3 = 16 กิโลเมตร

            เส้นทางที่   6 A, C, D, E ระยะทางยาว 5 + 3 + 3 = 11 กิโลเมตร

            เส้นทางที่   7 A, C, D, F, E ระยะทางยาว 5 + 3 + 2 + 2 = 12 กิโลเมตร

            จะเห็นว่าเส้นทางที่   1 A, B, D, E ระยะทางยาว 4 กิโลเมตรเป็นระยะทางที่สั้นที่สุด

            ฉะนั้นในตัวอย่างข้างต้น จะเห็นว่า วิถี A, B, D, E เป็นวิถีที่สั้นที่สุด

สำหรับกราฟถ่วงนำหนักที่มีจุดยอดและเส้นเชื่อมเป็นจำนวนมาก การหาวิถี A - Z ที่สั้นที่สุด

โดยการค้นหาวิถี A - Z ทั้งหมดแล้วเลือกวิถีที่ผลรวมของค่าน้ำหนักน้อยที่สุด ทำได้ไม่สะดวกและเสียเวลา ในการหาวิถี A - Z ที่สั้น

 ที่สุดมีขั้นตอนวิธีที่ใช้หาวิถีที่สั้นที่สุด เช่น ขั้นตอนวิธีของ Dijkstra

    

    

     ในที่นี้เราจะศึกษา ขั้นตอนวิธีของ Dijkstra พร้อมแสดงตัวอย่าง จงหาวิถี A - H ที่สั้นที่สุดของกราฟต่อไปนี้

            จากกราฟข้างต้น เราได้ว่า   

            วิถี A-H ที่สั้นที่สุดคือ A, B, E, H

            วิถี A-D ที่สั้นที่สุดคือ A, C, D

            วิถี A-G ที่สั้นที่สุดคือ A, C, G 

            วิถี A-F ที่สั้นที่สุดคือ A, B, F  หมายเหตุ      จากขั้นตอนวิธีของ Dijkstra ข้างต้นเราจะได้วิถีที่สั้นที่สุดจาก A ไปยังจุดยอดใดๆ                    เท่านั้น ถ้าเราจะหาวิถีที่สั้นที่สุดจากจุดยอดที่ไม่ใช่จุด A จะต้องเริ่มขั้นตอนวิธีของ Dijkstra ใหม่