อัลกอริทึมในการหาเส้นทางที่สั้นที่สุด

อัลกอริทึมในการหาเส้นทางที่สั้นที่สุด (Shortest Paths Algorithm)

ในกราฟที่มีน้ำหนัก หากเอาไปแทนระยะทางระหว่างจังหวัดต่าง ๆ ดังตัวอย่างข้อที่ 9.5 น้ำหนักอาจหมายถึงระยะทางเป็นกิโลเมตร หรือเวลาเดินทางเป็นชั่วโมง หรือค่าตั๋วโดยสาร ฯลฯ ปัญหาลักษณะนี้จึงเป็นเรื่องที่น่าศึกษาเพื่อหาเส้นทางที่มีน้ำหนักน้อยที่สุดจากเวอร์เทกซ์ที่กำหนดไปยังเวอร์เทกซ์อื่น ๆ ทุกเวอร์เทกซ์ในกราฟที่มีเส้นทางไปถึง หรือเรียกว่า เส้นทางที่สั้นที่สุดจากจุดเดียว (Single Source Shortest Path) อัลกอริทึมที่ใช้เพื่อแก้ปัญหานี้รู้จักในชื่ออัลกอริทึมของ ดิจสตรา ( Dijkstra’ Algorithm) ซึ่งเป็นชื่อของนักคณิตศาสตร์ ชาวดัทช์ (Dutch) ผู้เสนอวิธีการแก้ปัญหานี้ในปี ค.ศ. 1959

ข้อจำกัดประการหนึ่งของอัลกอริทึมข้างต้น คือ ค่าน้ำหนักของเอดจ์ต้องมีค่าไม่น้อยกว่า 0 (Non Negative) ส่วนกราฟจะเป็นแบบมีทิศทางหรือไม่ก็ได้ แต่ต้องเป็นกราฟที่ต่อถึงกัน (Connected) กล่าวคือ จะต้องมีเส้นทาง (Path) ระหว่างทุก ๆ เวอร์เทกซ์ของกราฟ

Dijkstra’s Algorithm คล้ายกับอัลกอริทึมของการค้นหาในแนวกว้าง แต่จะต้องเพิ่มส่วนของน้ำหนักในแต่ละเวอร์เทกซ์ เพื่อแสดงน้ำหนักจากเวอร์เทกซ์ตั้งต้นจนถึงเวอร์เทกซ์นั้น เราสามารถกำหนดค่าเริ่มต้น (Initialize) ให้กับเวอร์เทกซ์ตั้งต้นให้มีน้ำหนัก 0

น้ำหนักที่เวอร์เทกซ์ใด ๆ สามารถหาได้จาการหาผลบวกของน้ำหนักเอดจ์จากเวอร์เทกซ์ตั้งต้นถึงเวอร์เทกซ์นั้น

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

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

(Greedy Algorithm)

จากอัลกอริทึมในหัวข้อ 9.12 ที่ผ่านมา สามารถนำมาหาเส้นทางที่สั้นที่สุด เริ่มด้วยกำหนดค่าให้เวอร์เทกซ์ตั้งต้น ในที่นี้คือเวอร์เทกซ์ B ให้มีน้ำหนัก 0 (ศูนย์) จากนั้นให้ดำเนินการดังนี้

รอบแรก

อัลกอริทึมเพื่อการหาเส้นทางที่สั้นที่สุด

สรุปเป็นแนวทางได้ดังนี้

initMarks (graph)

clearPriorityQ (pqueue)

enPQ (pqueue, startVertex

do

dePQ (pqueue, vertex)

if (NOT vertexMarked)

markVertex (vertex)

getAdjacencyVertices (adjList)

updateVertexWeight (graph, vertex,Weight)

enPQ (pqueue, adjList)

while (NOT emptyPQ (pqueue))

วิธีการหาเส้นทางที่สั้นที่สุด

ต่อไปนี้เป็นตัวอย่าง การหาเส้นทางที่สั้นที่สุด จากกราฟที่กำหนดให้ โดยเริ่มจากเวอร์เทกซ์ B

รอบที่ 3

รอบที่ 4

รอบที่ 5

รอบที่ 6

รอบที่ 7

About these ads

ใส่ความเห็น

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 / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

ติดตาม

Get every new post delivered to your Inbox.

%d bloggers like this: