Кратчайший путь в ациклическом графе

Принцип оптимальности на префиксе

Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)
[math]a \rightsquigarrow b \rightsquigarrow c [/math]
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.

Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.
В общем случае мы можем написать:
[math]opt[u] = min_{v,u \in E} (opt[v] + cost(vu))[/math], где cost(vu) - вес ребра из u в v