Introduction to Graph Theory part 8 : Shortest-path problems

• Part 1
• Part 2
• Part 3
• Part 4
• Part 5
• Part 6
• Part 7

เนื้อหาในหลายตอนที่ผ่านมาน่าจะทำให้เห็นภาพว่าตัวแบบ graph สามารถนำไปช่วยแก้ปัญหาในหลายเรื่อง ตัวแบบเดียวอาจนำไปใช้แก้ปัญหามากกว่า 1 ด้าน เช่น การวางแผนการเดินทาง เราแทนที่เมืองด้วย vertex ถ้าต้องการหาเส้นทางที่สั้นที่สุด ก็แทนที่ระยะทางระหว่างเมืองด้วย edges ที่ระบุขนาดเป็นค่าของระยะทาง หากต้องการคำนวณค่าใช้จ่ายก็แทนที่ค่า edges ด้วยค่าใช้จ่าย โดยที่ไม่ต้องเปลี่ยนตัวแบบ graph ตัวแบบ marriage problem ก็ไม่ได้ใช้แต่ในการจับคู่แต่งงานเท่านั้น แต่ใช้กับงานอื่นที่เกี่ยวข้องกับการจับคู่ได้ เช่น การจ่ายงาน (job assignment) การจัดแผนการรักษาโรคของหมอ ฯลฯ เนื้อหาในตอนนี้จะกล่าวถึงตัวแบบปัญหาที่พบได้บ่อยที่สุดในเรื่องการ graph นั่นคือ การหาระยะทางหรือต้นทุนที่น้อยที่สุดระหว่าง 2 vertex ใดๆใน graph ซึ่งผลที่ได้อาจไม่ใช่การเดินผ่านจำนวน vertices ที่น้อยที่สุดก็ได้ เช่น ต้องการหาต้นทุนค่า flight tickets ขั้นประหยัดจากประเทศไทยไปฟิลิปปินส์ การบินผ่านบางประเทศอาจมีค่าใช้จ่ายน้อยกว่าก็ได้

รูปที่ 1 ตัวแบบ graph ของค่า flight ticket ชั้น economic class ระหว่างประเทศ

Algorithm แก้ปัญหา shortest path มีหลายวิธีได้แก่

  • Dijkstra's algorithm (ไดจ์คสตรา)

  • Depth First Search (DFS)

  • Breadth First Search (BFS)

  • A*

  • Bellman Ford's algorithm

เนื้อหาในตอนนี้จะกล่าวถึง Dijkstra's algorithm เนื่องจากเป็น algorithm พบได้ค่อนข้างบ่อยกว่าแบบอื่น

Dijkstra's algorithm

ข้อดีของ algorithm นี้คือสามารถใช้ได้ทั้ง directed และ undirected weighted graph การทำงานจะอิงการใช้ตารางเก็บข้อมูลคล้ายกับ adjacency matrix

ขั้นตอน

1. ต้องกำหนด vertex เริ่มต้นก่อน จะเป็น vertex ใดก็ได้เพื่อใช้เป็นจุดเริ่มต้นสำหรับหาต้นทุน (cost) จาก vertex นี้ไปยัง vertices อื่นที่เหลือใน graph จากตัวอย่าง สมมุติให้ A คือจุดเริ่มต้น

2. สร้างตารางเพื่อใช้เก็บข้อมูลต้นทุนที่ต้องใช้และเส้นทางการเข้าถึง (path) และกำหนดค่าต้นทุนเริ่มต้นของการเดินทางเป็น $\mathrm{\infty }$ อาจใช้ค่าอื่นที่มั่นใจว่าผลรวมของต้นทุนทั้งหมดใน graph จะไม่มากกว่าค่านี้

From A to	Total Cost	From
A	0
B	$\mathrm{\infty }$
C	$\mathrm{\infty }$
D	$\mathrm{\infty }$
E	$\mathrm{\infty }$

3. ไปที่ adjacent vertices ของ A ซึ่่งคือ B และ C แล้วดูค่าต้นทุนการเดินทางจาก graph

  3.1  จาก A ไป B มีต้นทุน 50 เทียบกับค่าที่ให้ไว้ตารางแล้วน้อยกว่า $\mathrm{\infty }$ ทำการปรับค่าต้นทุนในตารางให้เป็นค่าที่น้อยกว่า

  3.2  จาก A ไป C มีต้นทุน 80 ซึ่งน้อยกว่าค่า $\mathrm{\infty }$ ในตาราง ทำการปรับค่าต้นทุนในตารางให้เป็นค่าที่น้อยกว่า

From A to	Total Cost	From
A	0
B	50	A
C	80	A
D	$\mathrm{\infty }$
E	$\mathrm{\infty }$

4. จากตาราง adjacent ของ B มี C และ D

  4.1  จาก B ไป C (ดูตารางแถวของ C) มีต้นทุน 90 รวมต้นทุนเดิม(ในแถวของ B) อีก 50 แล้วเป็น 140 ตีความว่าต้นทุนจาก A ไป C โดยผ่าน B มีต้นทุนรวม 140 ซึ่งมากกว่าค่าต้นทุนในตาราง (จาก A ไป C ทางตรงมีค่า 80) ดังนั้นจะไม่มีการปรับค่าต้นทุนในตารางในแถวของ C

  4.2  จาก B ไป D (ดูตารางแถวของ D) มีต้นทุน 60 รวมของเดิมอีก 50 (ในแถวของ B) เป็น 110 ซึ่งน้อยกว่าค่า $\mathrm{\infty }$ ในตาราง ทำการปรับค่าต้นทุนในตารางในถวของ Dให้เป็น 110

From A to	Total Cost	From
A	0
B	50	A
C	80	A
D	110	B
E	$\mathrm{\infty }$

5. ต่้อไปเริ่มจาก C มี adjacent คือ D และ E

  5.1  จาก C ไป D (ดูตารางแถวของ D) มีต้นทุน 20 รวมต้นทุนเดิม(ในแถวของ C) อีก 80 แล้วเป็น 100 ตีความว่าต้นทุนจาก A ไป D โดยผ่าน C มีต้นทุนรวม 100 ซึ่งมากกว่าค่าต้นทุนในตาราง (จาก A ไป D ผ่าน B มีค่า 110) ดังนั้นจะปรับค่าต้นทุนในตารางในแถวของ D เป็น 100

  5.2  จาก C ไป E (ดูตารางแถวของ D) มีต้นทุน 70 รวมต้นทุนเดิม(ในแถวของ C) อีก 80 แล้วเป็น 150 น้อยกว่าค่า $\mathrm{\infty }$ ในตาราง ปรับค่าต้นทุนในตารางเป็น 150

From A to	Total Cost	From
A	0
B	50	A
C	80	A
D	100	C
E	150	C

6. ต่อไปเริ่มจาก D มี adjacent คือ E มีต้นทุน 40 รวมต้นทุนเดิม(ในแถวของ D) อีก 100 เป็น 140 น้อยกว่าค่าในตาราง ทำการปรับค่าต้นทุนและ path ในตาราง

From A to	Total Cost	From
A	0
B	50	A
C	80	A
D	100	C
E	140	D

7. ต่อไปเริ่มจาก E มี adjacent คือ B มีต้นทุน 50 รวมต้นทุนเดิม(ในแถวของ E) อีก 140 เป็น 190 มากกว่ากว่าค่าในตาราง (ดูแถว B) ซึ่งมีค่า 50 ไม่ต้องปรับแก้ใด สุดท้ายจะได้ graph ที่แสดงต้นทุนต่ำที่สุดในการเดินทางจากต้นทาง A ไปยัง vertex ต่างๆ ดังรูปที่

ถ้ายังจำเรือง Prim's algorithm ได้ จะเห็นว่า มีความคล้ายคลึงกันมาก ความต่างอยู่ที่ Prim's algorithm ใช้มุมมองหาต้นทุนทีตำ่ที่สุดจาก vertex ที่กำลังอยู่ในขณะนั้น ในขณะที่ Dijkstra's algorithm ใช้ผลรวมของต้นทุนทั้งหมดนับจากจุดเริ่มต้น