46
правок
Изменения
Нет описания правки
{{Кратчайший путь из u в v |definition= – это любой путь p из u в v, для которого <math>\boldsymbol w(p) = \delta(u, v)</math>, где: <br>
* <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> - в противном случае
}}
==Принцип оптимальности на префиксе==
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
