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 ที่สั้นที่สุดในกราฟ (ถ้ากราฟไม่มี cycle อัลกอริทึมนี้จะตอบ no) อัลกอริทึมของคุณควรทำงานได้ในเวลา $O(|V|^{3})\,$