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

ข้อนี้ใช้อัลกอริทึมของ Bellman-Ford ได้เลย และเวลาการทำงานของ Bellman-Ford คือ $O(|V||E|)\,$ แต่เนื่องจากโจทย์ข้อนี้บอกว่าเส้นทางทางที่สั้นที่สุดระหว่างโหนดสองโหนดในกราฟมีอย่างมาก $k\,$ edge ดังนั้นจึงทำให้เวลาการทำงานเป็น $O(k|E|)\,$ นั่นเอง