Изменения

Перейти к: навигация, поиск

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

63 байта убрано, 22:25, 15 января 2011
Нет описания правки
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <tex>\boldsymbol w(p) = \delta(u, v)</tex>, где: <br>
* <tex>\boldsymbol w(p)</tex> = сумма весов всех ребер пути p
*<tex>\boldsymbol rm{\delta }(u,v) = \left\{\begin{casesarray}{llcl} \boldsymbol {min} \text{ } \boldsymbol \omega(p) : \text{for all ways p from u to v},;& if \mboxtext{if } \mathcal{9} p \\\mathcal{1}, ;& if \mboxtext{if }\nexists p\mbox { в противном случае}\\end{casesarray} \right.</tex>
}}
 
 
 
==Принцип оптимальности на префиксе==
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
Анонимный участник

Навигация