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