2
правки
Изменения
м
<code> '''count'''(g, v)
'''return''' d[v]
</code>
→Псевдокод
</tex>
'''if''' w[v]
'''else'''
sum = 0
'''for'''(всех <tex>c</tex> смежных с <tex>'''in''' g[v</tex>)] sum += '''count'''(g, c)
d[v] = sum
w[v] = true
'''return''' sum
'''countPaths'''(g, s, t)
d[s] = 1
w[s] = '''true'''
answer = '''count'''(t)
'''return''' answer
Значение функции <tex>count(v)</tex> считается для каждой вершины один раз, а внутри нее рассматриваются все такие ребра <tex>\{e\ |\ end(e) = v\}</tex>. Всего таких ребер для всех вершин в графе <tex>O(E)</tex>, следовательно, время работы алгоритма в худшем случае оценивается как <tex>O(V+E)</tex>, где <tex>V</tex> - количество вершин графа, <tex>E</tex> - количество ребер.
