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

ข้อ 1

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

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

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