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