Кратчайший путь в ациклическом графе — различия между версиями
Кирилл (обсуждение | вклад) |
Кирилл (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
{{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <math>\boldsymbol w(p) = \delta(u, v)</math>, где: <br> | {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <math>\boldsymbol w(p) = \delta(u, v)</math>, где: <br> | ||
* <math>\boldsymbol w(p)</math> = сумма весов всех ребер пути p | * <math>\boldsymbol w(p)</math> = сумма весов всех ребер пути p | ||
| − | *<math>\boldsymbol \delta(u,v) = \boldsymbol {min} | + | *<math>\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} </math> | ||
}} | }} | ||
==Принцип оптимальности на префиксе== | ==Принцип оптимальности на префиксе== | ||
Версия 20:41, 12 декабря 2010
| Определение: |
Кратчайший путь из u в v – это любой путь p из u в v, для которого , где:
|
Принцип оптимальности на префиксе
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.
В общем случае мы можем написать:
, где cost(vu) - вес ребра из u в v
