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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
*<tex>\rm{\delta}(u, v) = \left\{\begin{array}{llcl}
 
*<tex>\rm{\delta}(u, v) = \left\{\begin{array}{llcl}
  
min \text{ } \omega(p) \text{ for all ways p from u to v} ;&if  \text{ }\mathcal{9} p  \\
+
min \text{ } \omega(p) \text{ for all ways p from u to v} &;if  \text{ }\mathcal{9} p  \\
\mathcal{1};&if \text{ } \nexists p\\
+
\mathcal{1}&;if \text{ } \nexists p\\
 
\end{array}\right.
 
\end{array}\right.
 
</tex>
 
</tex>

Версия 22:30, 15 января 2011

Определение:
Кратчайший путь из u в v – это любой путь p из u в v, для которого [math] w(p) = \delta(u, v)[/math], где:
  • [math]\boldsymbol w(p) [/math] = сумма весов всех ребер пути p
  • [math]\rm{\delta}(u, v) = \left\{\begin{array}{llcl} min \text{ } \omega(p) \text{ for all ways p from u to v} &;if \text{ }\mathcal{9} p \\ \mathcal{1}&;if \text{ } \nexists p\\ \end{array}\right. [/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.
Будем обходить вершины в порядке, обратном к топологической сортировке.