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

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

Кратчайший путь из u в v – это любой путь p из u в v, для которого [math]\boldsymbol w(p) = \delta(u, v)[/math], где:

• [math]\boldsymbol w(p)[/math] = сумма весов всех ребер пути p
• [math]\boldsymbol \delta(u,v) = \boldsymbol {min}[/math] [math] \boldsymbol\omega(p)[/math] : по всем путям p из u в v, если существует путь u в v

[math]\mathcal{1}[/math] - в противном случае

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

Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)
[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