[Ред] Рішення
Скористаємося принципом оптимальності на префікс.
Нехай - функція, де - вага найкоротшого шляху з в. Ясно, що дорівнює. Нехай - вага ребра з в. Будемо обходити граф в порядку топологічної сортування. Отримуємо наступні співвідношення:
Так як ми обходимо граф в порядку топологічної сортування. то на -му кроці всім (такі, що існує ребро з в) уже присвоєні оптимальні відповіді, і, отже, також буде надано оптимальну відповідь.
[Ред] Реалізація
Реалізуємо даний алгоритм:
[Ред] Приклад
Граф з прикладу