418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II/เฉลยข้อ 5 - ประวัติรุ่นแก้ไข

Cardcaptor เมื่อ 12:02, 4 ตุลาคม 2552

2009-10-04T12:02:38Z

Aoy: หน้าที่ถูกสร้างด้วย 'จากโจทย์กราฟที่ให้มาเป็นกราฟแบบมีทิศทาง ที่เป็…'

2009-10-03T15:01:50Z

หน้าที่ถูกสร้างด้วย 'จากโจทย์กราฟที่ให้มาเป็นกราฟแบบมีทิศทาง ที่เป็…'

หน้าใหม่

จากโจทย์กราฟที่ให้มาเป็นกราฟแบบมีทิศทาง ที่เป็น strongly connected คือสำหรับโหนดสองโหนด <math> u,v \in V \,</math> ใด ๆ ในกราฟแล้วจะมีเส้นทางจาก <math> u \,</math> ไปถึง <math> v \,</math> เสมอ ซึ่งโจทย์ข้อนี้ต้องการให้เราหาระยะทางที่สั้นที่สุดสำหรับทุกคู่ของโหนดที่ผ่านจุด <math> v_0 \,</math> ที่ให้มา พิจารณาโหนดสองโหนด <math> u,v \in V \,</math> ในกราฟ เราจะได้ว่าระยะทางที่สั้นที่สุดจากโหนด <math> u \, </math> ไปยังโหนด <math> v \,</math> โดยผ่านจุด <math> v_0 \,</math> ก็คือระยะทางที่สั้นที่สุดจากโหนด <math> u \,</math> ไปยังจุด <math> v_0 \,</math> และจากจุด <math> v_0 \,</math> ไปยังโหนด <math> v \,</math> นั่นเอง

การหาระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปยังโหนดทุกโหนดในกราฟ สามารถทำได้โดยการรันอัลกอริทึมในการหา shortest path ซักตัวโดยเริ่มจากจุด <math> v_0 \,</math> เราก็จะได้ระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปยังทุกโหนดในกราฟแล้ว จากนั้นเราจะทำการหากราฟผันกลับ <math> G^R \,</math> ของกราฟที่ให้มา แล้วทำการรันอัลกอริทึมในการหาเส้นทางที่สั้นที่สุดโดยเริ่มจากจุด <math> v_0 \,</math> ซึ่งเส้นทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปหาทุกโหนดที่ได้ในกราฟ <math> G^R \,</math> นี้จะเป็น ระยะทางที่สั้นที่สุดจากทุกโหนดไปยังจุด <math> v_0 \,</math> ในกราฟ <math> G \,</math> นั่นเอง หลังจากนั้นคำตอบก็คือเอาเส้นทางที่สั้นที่สุดจากทุกโหนดไปหาจุด <math> v_0 \,</math> มาต่อกับระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปหาทุกโหนดในกราฟนั่นเอง

เวลาการทำงานของอัลกอริทึมข้างต้นจะเป็นเวลาการทำงานของอัลกอริทึมในการหาเส้นทางที่สั้นที่สุด สมมติให้ใช้ DFS ดังนั้น เวลาส่วนนี้จะเป็น <math> O(|V||E|) \,</math> และ
จากโจทย์ข้อ 2 เรื่องโจทย์ปัญหาเกี่ยวกับกราฟเราสามารถหากราฟผันกลับ <math> G^R \,</math> ของกราฟ <math> G \,</math> ที่ให้มาได้โดยใช้เวลา <math> O(|V|+|E|) \,</math> ส่วนเวลาในการต่อเส้นทางที่สั้นที่สุดเข้าด้วยกันตอนสุดท้ายใช้เวลาอีก <math> O(|V||E|) \,</math> ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมนี้จึงเป็น <math> O(|V||E|)+O(|V|+|E|)+O(|V||E|)+O(|V||E|)=O(|V||E|) \,</math>

@@ แถว 3: / แถว 3: @@
 การหาระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปยังโหนดทุกโหนดในกราฟ  สามารถทำได้โดยการรันอัลกอริทึมในการหา shortest path ซักตัวโดยเริ่มจากจุด <math> v_0 \,</math> เราก็จะได้ระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปยังทุกโหนดในกราฟแล้ว  จากนั้นเราจะทำการหากราฟผันกลับ <math> G^R \,</math> ของกราฟที่ให้มา แล้วทำการรันอัลกอริทึมในการหาเส้นทางที่สั้นที่สุดโดยเริ่มจากจุด <math> v_0 \,</math> ซึ่งเส้นทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปหาทุกโหนดที่ได้ในกราฟ <math> G^R \,</math> นี้จะเป็น ระยะทางที่สั้นที่สุดจากทุกโหนดไปยังจุด <math> v_0 \,</math> ในกราฟ <math> G \,</math> นั่นเอง หลังจากนั้นคำตอบก็คือเอาเส้นทางที่สั้นที่สุดจากทุกโหนดไปหาจุด <math> v_0 \,</math> มาต่อกับระยะทางที่สั้นที่สุดจากจุด <math> v_0 \,</math> ไปหาทุกโหนดในกราฟนั่นเอง
-เวลาการทำงานของอัลกอริทึมข้างต้นจะเป็นเวลาการทำงานของอัลกอริทึมในการหาเส้นทางที่สั้นที่สุด สมมติให้ใช้ DFS ดังนั้น เวลาส่วนนี้จะเป็น <math> O(|V||E|) \,</math> และ
+เวลาการทำงานของอัลกอริทึมข้างต้นจะเป็นเวลาการทำงานของอัลกอริทึมในการหาเส้นทางที่สั้นที่สุด สมมติให้ใช้ Bellman-Ford algorithm ดังนั้น เวลาส่วนนี้จะเป็น <math> O(|V||E|) \,</math> และ
 จากโจทย์ข้อ 2 เรื่องโจทย์ปัญหาเกี่ยวกับกราฟเราสามารถหากราฟผันกลับ <math> G^R \,</math> ของกราฟ <math> G \,</math> ที่ให้มาได้โดยใช้เวลา <math> O(|V|+|E|) \,</math> ส่วนเวลาในการต่อเส้นทางที่สั้นที่สุดเข้าด้วยกันตอนสุดท้ายใช้เวลาอีก <math> O(|V||E|) \,</math> ดังนั้นเวลาการทำงานทั้งหมดของอัลกอริทึมนี้จึงเป็น <math> O(|V||E|)+O(|V|+|E|)+O(|V||E|)+O(|V||E|)=O(|V||E|) \,</math>