กราฟที่มีน้ำหนัก (Weighted Graphs)

กราฟที่มีน้ำหนัก (Weighted Graphs)

กราฟที่มีน้ำหนัก คือ กราฟที่แต่ละเอดจ์จะมีค่าบ่งบอกถึงความหมายอย่างใดอย่างหนึ่งอยู่

ด้วย ซึ่งค่านี้อาจหมายถึง ระยะทาง ความเร็ว เวลาเดินทาง ค่าโดยสาร ฯลฯ กราฟที่มีน้ำหนัก สามารถนำมาประยุกต์ใช้กับงานที่จำเป็นต้องคำนึงถึงค่าของเอดจ์

ตัวอย่าง กราฟแสดงเส้นทางการเดินทางระหว่างเมือง โดยที่แต่ละเอดจ์ของกราฟจะมีค่าน้ำหนัก ซึ่งแสดงถึงระยะทางระหว่างเมือง

จากกราฟข้างต้นใช้เวอร์เทกซ์แทนจังหวัด และเอดจ์แทนระยะทางระหว่างจังหวัด หากต้องการเดินทางจากชลบุรีไปปราจีนบุรี เราต้องมองหาเส้นทางการเดินทางระหว่างสองจังหวัดนี้ พบว่ามีหลายเส้นทางที่สามารถใช้เดินทางจากชลบุรีไปปราจีนบุรี เช่น

ชลบุรี ฉะเชิงเทรา ปราจีนบุรี รวมระยะทาง 119 กม.

ชลบุรี ฉะเชิงเทรา นครนายก ปราจีนบุรี รวมระยะทาง 172 กม.

ชลบุรี ระยอง ฉะเชิงเทรา ปราจีนบุรี รวมระยะทาง 314 กม.

ฯลฯ

หากเลือกเส้นทางใดเส้นทางหนึ่ง เราสามารถหาระยะทางรวมของการเดินทางนี้ได้ ด้วยการรวมค่าน้ำหนักของเอดจ์ทุกตัวที่เชื่อมโยงเส้นทางไปยังจังหวัดที่เราเลือกเดินทาง

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s