46
правок
Изменения
Нет описания правки
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <math>\boldsymbol w(p) = \delta(u, v)</math>, где: <br>
* <math>\boldsymbol w(p)</math> = сумма весов всех ребер пути p
*<math>\boldsymbol \delta(u,v) = \begin{cases} \boldsymbol {min}</math> <math> \text{ } \boldsymbol\omega(p)</math> : по всем путям \text{for all ways p из from u в to v}, если существует путь u в v & \mbox{if } \mathcal{9} p \\<math>\mathcal{1}, & \mbox{if }\nexists p\mbox { в противном случае}\end{cases}</math> - в противном случае
}}
==Принцип оптимальности на префиксе==
