418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 1

สังเกตว่าในกราฟนี้ทุก edge มีความยาวเป็น 1 ดังนั้นเราจึงาสามารถหา shortest path จาก u ไป v ได้ด้วย breadth first search (BFS)

ในการแก้ปัญหาในโจทย์ เราจะพยายามแก้ปัญหาที่เป็นแนวทั่วไปมากขึ้น กล่าวคือเราจะไม่หาจำนวน shortest path ที่แตกต่างกันจาก $u\,$ ไปยัง $v\,$ เท่านั้น แต่เราจะทำการหาคำนวณอะเรย์ $M[\cdot ]\,$ โดยที่ $M[w]\,$ มีค่าเท่ากับจำนวน shortest path จาก $u\,$ ไปยัง $w\,$ เมื่อ $w\,$ เป็น vertex ใดๆ ในกราฟ

อันดับแรก สังเกตว่า $M[u]=1\,$ เนื่องจาก shortest path จาก $u\,$ ไปยัง $u\,$ มีอยู่ path เดียวคือ path ความยาว 0 ที่เริ่มที่ $u\,$ แล้วไม่เคลื่อนต่อไปไหน

ต่อไป ให้ $w\,$ เป็น vertex ใดๆ ในกราฟ สมมติว่า shortest path จาก $u\,$ ไปยัง $w\,$ มีความยาว $\ell \,$ edge เราจะได้ว่า

$M[w]=M[x_{1}]+M[x_{2}]+\dotsb +M[x_{k}]$ (*)

เมื่อ $x_{1},x_{2},\ldots ,x_{k}\,$ คือ vertex ทั้งหมดที่

1. ความยาวของ shortest path จาก $u\,$ ไปยัง $x_{i}\,$ มีค่าเท่ากับ $\ell -1\,$ และ
2. มี edge $\{x_{i},w\}\,$ อยู่ในกราฟ สำหรับทุกๆ $i\,$

ที่เป็นเช่นนี้เพราะว่าสำหรับ path ความยาว $\ell \,$ จาก $u\,$ ไปถึง $w\,$ ทุก path จะมี vertex สุดท้ายก่อนจะไปถึง $w\,$ สมมติให้ vertex สุดท้ายนั้นเป็น $x\,$ เราจะได้ว่า

ความยาวของ shortest path จาก $u\,$ ไปยัง $x\,$ จะต้องเป็น $\ell -1\,$

(ัอันดับแรก ความยาวของ shortest path จาก $u\,$ ไปยัง $x\,$ จะมีค่ามากที่สุดเท่ากับ $\ell -1\,$ เนื่องจาก path จาก $u\,$ ไปถึง $x\,$ ก่อนที่จะไป $w\,$ มีความยาว $\ell -1\,$ อยู่แล้ว อันดับที่สอง shortest path จาก $u\,$ ไปถึง $x\,$ จะสั้นกว่า $\ell -1\,$ ไม่ได้ เนื่องจากถ้ามันสั้นกว่านั้นความยาวของ shortest path จาก $u\,$ ไปถึง $w\,$ ก็จะสั้นลงด้วย)

ด้วยเหตุนี้ สำหรับ shortest path จาก $u\,$ ไปถึง $x\,$ หนึ่ง path จะทำให้เกิด shortest path จาก $u\,$ ไปถึง $w\,$ หนึ่ง path ด้วย (กล่าวคือเราเดินจาก $u\,$ ไปถึง $x\,$ แล้วเดินต่อจาก $x\,$ ไปยัง $w\,$ โดยผ่าน edge $\{x,w\}\,$) สมการ (*) จีงเป็นความจริง

จากสมการ (*) เราจึงสามารถคำนวณอะเรย์ $M[w]\,$ ได้ดังต่อไปนี้

1. รัน breadth first search บนกราฟโดยเริ่มจาก $u\,$ แล้วให้แต่ละ vertex $w\,$ แต่ละ vertex จำระดับของมัน (ซึ่งมีค่าเท่ากับความยาวของ shortest path จาก $u\,$ ถึง $w\,$) ไว้ในอะเรย์ $L[w]\,$
2. สร้างอะเรย์ $M\,$ ให้มีขนาดใหญ่เท่ากับจำนวน vertex ในกราฟ และเซตให้ $M[w]=0\,$ สำหรับ vertex $w\,$ ทุกๆ vertex
3. ไล่ vertex $x\,$ ทีละเวอร์เท็กซ์ โดยไล่จากค่า $L[x]\,$ น้อยไปยังค่า $L[x]\,$ มาก

   พิจารณา edge $(x,w)\,$ ที่ออกจาก $x\,$ ทุก edge

   ถ้า $L[w]=L[x]+1\,$ แล้ว เซตให้ $M[w]=M[w]+M[x]\,$

เมื่ออัลกอริทึมทำงานเสร็จ เราจึงสามารถคืน $M[v]\,$ เป็นคำตอบได้

อัลกอริทึมข้างบนทำงานโดยใช้เวลา $O(|V|+|E|)\,$ เนื่องจาก breadth first search ทำงานได้ในเวลา $O(|V|+|E|)\,$ และ loop ในข้อ 3 ก็ทำงานในเวลา $O(|V|+|E|)\,$ เช่นกันเนื่องจากมันเข้าถึง edge แต่ละ edge เพียงครั้งเดียวเท่านั้น