1632
правки
Изменения
м
w[v] = true
rollbackEdits.php mass rollback
{{Задача
|definition = Задан [[Основные определения теории графов|ациклический граф ]] <tex>G</tex> и две вершины <tex>s</tex> и <tex>t</tex>. Необходимо посчитать количество путей из вершины <tex>s</tex> в вершину <tex>t</tex> по рёбрам графа <tex>G</tex>.
}}
</noinclude>
s = 0
'''for''' to '''in''' g[v]
s += '''countcountPaths'''(g, to, t)
'''return''' s
<tex> count(v) = \left \{
\begin{array}{ll}
d[v], & w[v]=''true'' \\ \sum\limits_{c|cv \in E}count(c), & w[v]=false
\end{array}
\right.
'''else'''
sum = 0
w[v] = ''true''
'''for''' c '''in''' g[v]
sum += '''count'''(g, c)
d[v] = sum
'''return''' sum
'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''return''' answer
* [[Динамическое программирование]]
* [[Кратчайший путь в ациклическом графе]]
* [[Динамика по поддеревьямЗадача о расстановке знаков в выражении]]* [[Задача о порядке перемножения матриц]]
==Источники информации==
* Bender, MАкулич И.Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах.A— М.: Высшая школа, Farach-Colton, M1986. — 319 с. {{— ISBN 5-06-002663-}} The LCA Problem Revisited9. LATIN (2000), с. 88-94
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
