46
правок
Изменения
Новая страница: «=Кратчайший путь в ациклическом графе= Кратчайший путь из u в v – это любой путь p из u в v, для…»
=Кратчайший путь в ациклическом графе=
Кратчайший путь из 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) = \boldsymbol {min}</math> <math> \boldsymbol\omega(p)</math> : по всем путям p из u в v, если существует путь u в v
<math>\mathcal{1}</math> - в противном случае
==Принцип оптимальности на префиксе==
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
<math>a \rightsquigarrow b \rightsquigarrow c </math> <br>
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<br>
== ==
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br>
В общем случае мы можем написать: <br>
<math>opt[u] = min_{v,u \in E} (opt[v] + cost(vu))</math>, где cost(vu) - вес ребра из u в v
Кратчайший путь из 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) = \boldsymbol {min}</math> <math> \boldsymbol\omega(p)</math> : по всем путям p из u в v, если существует путь u в v
<math>\mathcal{1}</math> - в противном случае
==Принцип оптимальности на префиксе==
Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)<br>
<math>a \rightsquigarrow b \rightsquigarrow c </math> <br>
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.<br>
== ==
Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.<br>
В общем случае мы можем написать: <br>
<math>opt[u] = min_{v,u \in E} (opt[v] + cost(vu))</math>, где cost(vu) - вес ребра из u в v
