418341 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต II

ข้อ 1

[Dasgupta, Papadimitriou, Vazirani 4.5]โดยทั่วไปแล้วเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมักจะมีมากกว่าหนึ่งเส้นทาง จงออกแบบอัลกอริทึมที่ทำงานในเวลา linear time สำหรับปัญหาต่อไปนี้

อินพุต: กราฟแบบไม่มีทิศทาง $G=(V,E)\,$ ที่มี cost ของ edge ทุก edge เป็นหนึ่ง และให้โหนดมาสองโหนดคือ $u,v\in V\,$

เอาพุต: จำนวนของเส้นทางที่สั้นที่สุดที่แตกต่างกันจาก $u\,$ ไปยัง $v\,$

เฉลย

ข้อ 2

[Dasgupta, Papadimitriou, Vazirani 4.10]ให้กราฟแบบมีทิศทางพร้อมกับ cost ของแต่ละ edge (อาจมีค่าเป็นลบได้) โดยที่รับประกันว่าเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมีอย่างมาก $k\,$ edge จงออกแบบอัลกอริทึมที่หาเส้นทางที่สั้นที่สุดระหว่างโหนดสองโหนด $u\,$ และ $v\,$ โดยอัลกอริทึมดังกล่าวทำงานได้ในเวลา $O(k|E|)\,$

เฉลย

ข้อ 3

[Dasgupta, Papadimitriou, Vazirani 4.11]จงหาอัลกอริทึมที่รับอินพุตเป็นกราฟแบบมีทิศทางที่มี cost ของแต่ละ edge เป็นบวก และให้คำตอบเป็นความยาวของ cycle ที่สั้นที่สุดในกราฟ (ถ้ากราฟที่ให้มาเป็น DAG อัลกอริทึมนี้จะตอบไม่มี ) อัลกอริทึมของคุณควรทำงานได้ในเวลา $O(|V|^{3})\,$

เฉลย

ข้อ 4

[Dasgupta, Papadimitriou, Vazirani 4.12]จงหาอัลกอริทึมที่ทำงานได้ในเวลา $O(|V|^{2})\,$ สำหรับปัญหาต่อไปนี้

อินพุต: กราฟไม่มีทิศทาง $G=(V,E)\,$ ความยาวของ edge $l_{e}>0\,$ และ edge $e\in E\,$

เอาพุต:ความยาวของ cycle ที่สั้นที่สุดที่มี edge $e\,$ ที่ให้มาอยู่ใน cycle นั้น

เฉลย

ข้อ 5

[Dasgupta, Papadimitriou, Vazirani 4.14]ให้ strongly connected directed graph $G=(V,E)\,$ ที่ cost ของแต่ละ edge มีค่าเป็นบวกและ node $v_{0}\in V\,$ จงหาอัลกอริทึมที่มีเวลาทำงานเป็นพหุนานามที่ใช้หาเส้นทางที่สั้นที่สุดสำหรับทุกคู่ของ node โดยที่เส้นทางดังกล่าวจะต้องผ่าน node $v_{0}\,$

เฉลย