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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> <math> \boldsymbol\omega(p)</math> : по всем путям p из u в v, если существует путь u в v
+
*<math>\boldsymbol \delta (u,v) = \begin{cases} 
<math>\mathcal{1}</math> - в противном случае
+
\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, для которого [math]\boldsymbol w(p) = \delta(u, v)[/math], где:
  • [math]\boldsymbol w(p)[/math] = сумма весов всех ребер пути p
  • [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]

Принцип оптимальности на префиксе

Префикс оптимального решения сам является оптимальным решением (в другой подзадаче)
[math]a \rightsquigarrow b \rightsquigarrow c [/math]
Если ac - оптимальное решение , то и ab (префикс ac) тоже является оптимальным решением.

Для нахождения кратчайшего пути в графе заведем функцию переменную opt[x], в которой хранится длина кратчайшего пути до вершины х.
В общем случае мы можем написать:
[math]opt[u] = min_{v,u \in E} (opt[v] + cost(vu))[/math], где cost(vu) - вес ребра из u в v