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

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

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

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