Изменения
Нет описания правки
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <mathtex>\boldsymbol w(p) = \delta(u, v)</mathtex>, где: <br>* <mathtex>\boldsymbol w(p)</mathtex> = сумма весов всех ребер пути p*<mathtex>\boldsymbol \delta (u,v) = \begin{cases}
\boldsymbol {min} \text{ } \boldsymbol \omega(p) : \text{for all ways p from u to v},& \mbox{if } \mathcal{9} p \\
\mathcal{1}, & \mbox{if }\nexists p\mbox { в противном случае}
\end{cases} </mathtex>
}}
==Принцип оптимальности на префиксе==
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
<mathtex>a \rightsquigarrow b \rightsquigarrow c </mathtex> <br>
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<br>
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br>
В общем случае мы можем написать: <br>
<mathtex>opt[u] = min_{v,u \in E} (opt[v] + cost(vu))</mathtex>, где cost(vu) - вес ребра из u в v. <br>
Будем обходить вершины в порядке, обратном к топологической сортировке.
