Кратчайший путь в ациклическом графе — различия между версиями
(→) |
|||
| Строка 1: | Строка 1: | ||
| − | {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого < | + | {{Определение|definition= '''Кратчайший путь''' из '''u''' в '''v''' – это любой путь '''p''' из '''u '''в '''v''', для которого <tex>\boldsymbol w(p) = \delta(u, v)</tex>, где: <br> |
| − | * < | + | * <tex>\boldsymbol w(p)</tex> = сумма весов всех ребер пути p |
| − | *< | + | *<tex>\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 \\ | \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 { в противном случае} | \mathcal{1}, & \mbox{if }\nexists p\mbox { в противном случае} | ||
| − | \end{cases} </ | + | \end{cases} </tex> |
}} | }} | ||
==Принцип оптимальности на префиксе== | ==Принцип оптимальности на префиксе== | ||
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br> | Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br> | ||
| − | < | + | <tex>a \rightsquigarrow b \rightsquigarrow c </tex> <br> |
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<br> | Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<br> | ||
| Строка 15: | Строка 15: | ||
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br> | Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br> | ||
В общем случае мы можем написать: <br> | В общем случае мы можем написать: <br> | ||
| − | < | + | <tex>opt[u] = min_{v,u \in E} (opt[v] + cost(vu))</tex>, где cost(vu) - вес ребра из u в v. <br> |
Будем обходить вершины в порядке, обратном к топологической сортировке. | Будем обходить вершины в порядке, обратном к топологической сортировке. | ||
Версия 00:28, 11 января 2011
| Определение: |
Кратчайший путь из u в v – это любой путь p из u в v, для которого , где:
|
Принцип оптимальности на префиксе
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.
В общем случае мы можем написать:
, где cost(vu) - вес ребра из u в v.
Будем обходить вершины в порядке, обратном к топологической сортировке.
